最长回文子串实现——k-j-1如何获取回文子串的长度

Question

private void extendPalindrome(String s, int j, int k) {
    while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
        j--;
        k++;
    }
    if (maxLen < k - j - 1) {
        lo = j + 1;
        maxLen = k - j - 1;
    }
}

这如何得到回文子串的长度？例如，我们使用“racecar”这个词。 k-j-1 怎样才能得到长度？它会让我 6-0-1，也就是 5。

Answer 1

对我来说，代码看起来是正确的，尽管在不知道其余部分的情况下很难判断。

为什么是正确的？

这个方法可能是一个试图找到最大回文的方法的辅助程序。因此 maxLen 仅在找到的（扩展的，最大的）回文比目前找到的回文长时才被修改。这就是为什么我们只在 if-statement 而不是在 while 中修改 maxLen 的原因。但为什么是 k - j - 1 而不是 k - j + 1？这是因为在 while 中，如果字符匹配，则 j 递减，k 递增。这意味着循环后k比最后一个匹配字符大1，j小1。考虑到这一点，我们得到 (k - 1) - (j + 1) + 1。这是经过调整的公式。如果我们简化我们得到 (k - 1) - (j + 1) + 1 = k - 1 - j - 1 + 1 = k - j - 1。正是我们在代码中看到的。

顺便说一句，这也是为什么 lo 是 j + 1 而不仅仅是 j 的原因。

“赛车”示例将有 j = -1 和 k = 7，因此 maxLen = 7 - (-1) - 1 = 7 + 1 - 1 = 7。这是正确的。

最长回文子串实现——k-j-1如何获取回文子串的长度

Longest palindromic substring implementation- how k-j-1 gets the length of the palindromic substring

java

algorithm

palindrome