0

我一直在尝试解决寻找字符串最长回文的问题。虽然我可以通过中间元素来做到这一点，但我想通过 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
           }     
        }    
    }
}

我无法想到如何找到最长的回文？

我认为通过使用 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"));
}

}
4

2 回答 2

1 
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

于 2013-08-17T14:42:36.120 回答
0

所以，最后我发现你正在寻找字符串中最长的回文。观察回文的基本情况

对于任何给定的索引i（从 0 到字符串末尾）和j（从字符串末尾到 0）

  1. j 和 i 的索引相等。他们显然是平等的。单个字符串是回文。

  2. i 和 j 的索引正好相差 1。即。您正在比较连续的字符。如果它们相等，则您已找到 2 个字符的回文。

  3. 否则，我们有 2 种方法可以进入 step1或2.

    1. 考虑 index[i, j - 1] 中的字符串
    2. 考虑 index[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
于 2013-08-17T14:10:07.217 回答