最長的字符串迴文使用string.reverse

Question

我一直在試圖解決查找字符串的最長迴文的問題。 雖然我能夠通過將中間的元素做，但我想通過string.reverse嘗試一下：

這裏是我的代碼：

的疑問：我使用string.reverse找到的反向給定的字符串，然後試圖比較反向字符串和輸入字符串中的每個子字符串，但這不會給我最大的迴文，但它會給所有可能的迴文... 另外，我在某處做了一些錯誤，請幫助我發現...

public class StringPalindrome {  
    public static void main(String args[]) { 
    StringBuilder strBuilder = new StringBuilder("Shubham"); 
    StringBuilder a = new StringBuilder(""); 
    a = strBuilder.reverse(); //Reverse the string and saving it into other string 
    for(int i=0;i<strBuilder.length();i++){ // Loop one for begin index 
     for(int j=1;i<strBuilder.length() + 1;j++){ // Loop two for end index 
      if(a.substring(i, j).equals(strBuilder.substring(i, j))){ // comparing 
      System.out.println(strBuilder.substring(i, j)); //printing palindrome 
      }  
     }  
    } 
} 

我不能想到如何fin最長的迴文？

我想用string.reverse，這將是一個短代碼：

雖然我能做到這樣：

public class LongestPalindrome 
{ 

static public String expand(String string, int a, int b) 
{ 
if (a > b) 
return null; 
int left = a, right = b; 
while (left >= 0 && right < string.length() && string.charAt(left) == string.charAt(right)) 
{ 
left--; 
right++; 
} 
return string.substring(left + 1, right); 
} 

static public String longestPalindrome(String string) 
{ 
if (string == null) 
return null; 
String longest = string.substring(0, 1); 
for (int i = 0; i < string.length() - 1; i++) 
{ 
String palindrome = expand(string, i, i); 
if (palindrome.length() > longest.length()) 
{ 
longest = palindrome; 
} 
palindrome = expand(string, i, i + 1); 
if (palindrome.length() > longest.length()) 
{ 
longest = palindrome; 
} 
} 
return longest; 
} 

public static void main(String[] args) 
{ 
System.out.println(longestPalindrome("baraik")); 
} 

} 

Answer 1

所以，最後我發現你正在尋找爲一個字符串中最長的迴文。 觀察基礎案例爲迴文爲

對於任何給定索引我（從0前進到字符串的末尾）和Ĵ（其從所述字符串的末尾，以0前進）

1. j和i的指數是相等的。他們顯然是平等的。單字符串是迴文。

2. i和j的指數恰好相差1。您正在比較連續的字符。如果他們相同，你會發現一個2字符迴文。

3. 否則我們有2種方法可以進入步驟1或2。

   1. 考慮從指數[I，J - 1]串
   2. 考慮從索引字符串第[i + 1，j]的

   的上述2個條件最大給你的最長長度迴文。

4. 記憶步驟1,2,3從緩存中獲取值。

   這是一個打印所有迴文的示例實現。這是O（n ** 2）。

   public static int maxPalindrome(char ch[], int i, int j, int cache[][]) { 
       if (cache[i][j] != -1) { 
        return cache[i][j]; 
       } 
   
       if (i == j) { 
        return cache[i][j] = 1; 
       } 
   
       if (j - i == 1) { 
        return cache[i][j] = (ch[i] == ch[j] ? 2 : 0); 
       } 
   
       int max = 0; 
       //easy if they are equal 
       if (ch[i] == ch[j]) { 
        int inCount = maxPalindrome(ch, i + 1, j - 1, cache); 
        max = inCount == 0 ? 0 : 2 + inCount; 
       } 
       //there are 2 ways to go step 3 
       maxPalindrome(ch, i + 1, j, cache); 
   
       maxPalindrome(ch, i, j - 1, cache); 
       return cache[i][j] = max; 
   } 
   
   public static void main(String[] args) { 
       String str = "abbzbasddeeaaaccffertrecca"; 
       char ch[] = str.toCharArray(); 
       int cache[][] = new int[ch.length][ch.length]; 
       for (int row[] : cache) { 
        Arrays.fill(row, -1); 
       } 
       maxPalindrome(ch, 0, ch.length - 1, cache); 
       //print all the pallindromes 
       for (int i = 0; i < cache.length; ++i) { 
        for (int j = 0; j < cache.length; ++j) { 
         if (cache[i][j] > 0) { 
          System.out.println(str.substring(i, j+1) + " " + cache[i][j]); 
         } 
        } 
       } 
   
   } 
   

返回

bb 2 
bzb 3 
z 1 
dd 2 
ee 2 
aa 2 
aaa 3 
a 1 
aa 2 
cc 2 
ff 2 
ertre 5 
rtr 3 
t 1 
cc 2 

Answer 2

public class StringPalindrome {  
    public static void main(String args[]) { 
     int big=0; 
     String pstr =""; 
     StringBuilder str = new StringBuilder("aabbccabbabhhakllkjiooijpawan-nawap"); 
     for(int i=0;i<str.length()-1;i++) 
      for(int j=i+1;j<str.length();j++){ 
       if(str.charAt(i)== str.charAt(j) && pldrm(str.subSequence(i,j+1).toString()) && big<(j-i)){ 
          pstr=str.subSequence(i,j+1).toString(); 
          big=j-i; 
          } 
      } 
     System.out.println(pstr); 
      } 
    static boolean pldrm(String str){ 
     int length=str.length()-1; 
     for(int i=0;i<length;i++){ 
      if(str.charAt(i)!= str.charAt(length-i)) 
      return false; 
     } 
     return true; 
    } 
}  

輸出
pawan-nawap