題目:
輸入一個字符串s,我們可以刪除字符串s中的任意字符,讓剩下的字符串形成一個對稱字符串,且該字符串為最長對稱字符串。
例如:
最長對稱字符串存在多個,則輸出多個相同長度的最長對稱字符串。
輸入輸出示例:
public static void main(String[] args){
// TODO: 輸出最長對稱字符串: goog
String input1 = "google";
// TODO: 輸出最長對稱字符串: aca
String input2 = "abcda";
// TODO: 輸出最長對稱字符串: opo/upu
String input3 = "opo-upu";
}
https://www.cnblogs.com/yingp...
這個有個JAVA代碼,你可以參考下。我一開始是用C寫的,感覺太麻煩了,JAVA不太會,但是看懂了一點,希望可以幫到你
問題已經(jīng)解決
由于提供的代碼對于opo-upu
這樣的測試用例無法得到正確的結(jié)果,所以,參考了 @studio 和 Java——最長公共子串問題LCS提供的思路之后,編寫了如下代碼:
findLCS(String input): String 獲取最大回文串
private static String findLCS(String input) {
// 要返回的結(jié)果
StringBuilder result = new StringBuilder();
// 將字符串反轉(zhuǎn)
String reverse = new StringBuilder(input).reverse().toString();
// 字符串長度
int len = input.length();
// 矩陣 -> 二維數(shù)組
int[][] temp = new int[len][len];
// 橫向字符
char[] hor = input.toCharArray();
// 縱向字符
char[] ver = reverse.toCharArray();
// 給矩陣(二維數(shù)組賦值)
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
temp[i][j] = (hor[j] == ver[i]) ? 1 : 0;
}
}
// 找到第一個橫向
int horIndex = -1;
for (int i = 0; i < len - 1; i++) {
if (temp[0][i] == 1) {
horIndex = i;
}
}
// 找到第一個縱向
int verIndex = -1;
for (int i = 0; i < len - 1; i++) {
if (temp[i][0] == 1) {
verIndex = i;
}
}
// 處理特殊情況的標(biāo)識,如 abcda
boolean flag = false;
int indexHor = 0;
if (horIndex != -1 && horIndex != 0) {
for (int i = horIndex; i < len; i++) {
if (temp[indexHor++][i] == 1) {
result.append(hor[i]);
}
}
flag = true;
}
int indexVer = verIndex;
if (verIndex != -1) {
if (flag) {
result.append("/");
}
for (int i = 0; i < len - verIndex; i++) {
if (temp[indexVer++][i] == 1) {
result.append(hor[i]);
}
}
}
return result.toString();
}
main(String[] args): void 主方法
public static void main(String[] args) {
String input1 = "google";
String input2 = "abcda";
String input3 = "opo-upu";
System.out.println(input1 + " -> " + findLCS(input1)); // 結(jié)果: google -> goog
System.out.println(input2 + " -> " + findLCS(input2)); // 結(jié)果: abcda -> aca
System.out.println(input3 + " -> " + findLCS(input3)); // 結(jié)果: opo-upu -> opo/upu
}
北大青鳥APTECH成立于1999年。依托北京大學(xué)優(yōu)質(zhì)雄厚的教育資源和背景,秉承“教育改變生活”的發(fā)展理念,致力于培養(yǎng)中國IT技能型緊缺人才,是大數(shù)據(jù)專業(yè)的國家
北大青鳥中博軟件學(xué)院創(chuàng)立于2003年,作為華東區(qū)著名互聯(lián)網(wǎng)學(xué)院和江蘇省首批服務(wù)外包人才培訓(xùn)基地,中博成功培育了近30000名軟件工程師走向高薪崗位,合作企業(yè)超4
中公教育集團創(chuàng)建于1999年,經(jīng)過二十年潛心發(fā)展,已由一家北大畢業(yè)生自主創(chuàng)業(yè)的信息技術(shù)與教育服務(wù)機構(gòu),發(fā)展為教育服務(wù)業(yè)的綜合性企業(yè)集團,成為集合面授教學(xué)培訓(xùn)、網(wǎng)
達(dá)內(nèi)教育集團成立于2002年,是一家由留學(xué)海歸創(chuàng)辦的高端職業(yè)教育培訓(xùn)機構(gòu),是中國一站式人才培養(yǎng)平臺、一站式人才輸送平臺。2014年4月3日在美國成功上市,融資1
曾工作于聯(lián)想擔(dān)任系統(tǒng)開發(fā)工程師,曾在博彥科技股份有限公司擔(dān)任項目經(jīng)理從事移動互聯(lián)網(wǎng)管理及研發(fā)工作,曾創(chuàng)辦藍(lán)懿科技有限責(zé)任公司從事總經(jīng)理職務(wù)負(fù)責(zé)iOS教學(xué)及管理工作。
浪潮集團項目經(jīng)理。精通Java與.NET 技術(shù), 熟練的跨平臺面向?qū)ο箝_發(fā)經(jīng)驗,技術(shù)功底深厚。 授課風(fēng)格 授課風(fēng)格清新自然、條理清晰、主次分明、重點難點突出、引人入勝。
精通HTML5和CSS3;Javascript及主流js庫,具有快速界面開發(fā)的能力,對瀏覽器兼容性、前端性能優(yōu)化等有深入理解。精通網(wǎng)頁制作和網(wǎng)頁游戲開發(fā)。
具有10 年的Java 企業(yè)應(yīng)用開發(fā)經(jīng)驗。曾經(jīng)歷任德國Software AG 技術(shù)顧問,美國Dachieve 系統(tǒng)架構(gòu)師,美國AngelEngineers Inc. 系統(tǒng)架構(gòu)師。