java - 调试代码以查找字符串中的最长回文

Question

我试图理解在给定字符串中找到最长回文的代码片段。这是代码段

public static String longestPalindromeString(String in) {
        char[] input = in.toCharArray();
        int longestPalindromeStart = 0;
        int longestPalindromeEnd = 0;

        for (int mid = 0; mid < input.length; mid++) {
            // for odd palindrom case like 12321, 3 will be the mid
            int left = mid-1;
            int right = mid+1;
            // we need to move in the left and right side by 1 place till they reach the end
            while (left >= 0 && right < input.length) {
                // below check to find out if its a palindrome
                if (input[left] == input[right]) {
                    // update global indexes only if this is the longest one till now
                    if (right - left > longestPalindromeEnd
                            - longestPalindromeStart) {
                        longestPalindromeStart = left;
                        longestPalindromeEnd = right;
                    }
                }
                left--;
                right++;
            }
            // for even palindrome, we need to have similar logic with mid size 2
            // for that we will start right from one extra place
            left = mid-1;
            right = mid + 2;// for example 12333321 when we choose 33 as mid
            while (left >= 0 && right < input.length)
            {
                if (input[left] == input[right]) {
                    if (right - left > longestPalindromeEnd
                            - longestPalindromeStart) {
                        longestPalindromeStart = left;
                        longestPalindromeEnd = right;
                    }
                }
                left--;
                right++;
            }
        }
        // we have the start and end indexes for longest palindrome now
        return in.substring(longestPalindromeStart, longestPalindromeEnd + 1);
    }

}

"bb"但是，对于输入返回"b"和"abb"返回"a"而不是 bb ，代码段似乎失败了。

关于导致该错误的任何想法？

代码段的来源。

Answer 1

要解决此更改，请执行以下操作：

1. 在 while 中，当两个字符不相等时，添加一个 break 以从 while 中中断。

   while(/*....*/)
   {
        if(/*...*/)
        {
            //....
        }
        else           // add this
            break;     // and this   
   }
   

2. 偶数情况的左右初始设置是错误的。它假定中间的两个字符是相同的。将其更改为

   left = mid;
   right = mid+1;
   

这与原始代码的注释中所说的完全一样... -_- 我刚刚读过。