由于 String / StringBuilder 相等性导致的最长回文边缘案例

Question

此代码不适用于测试用例：aacabdkacaa，但适用于 babad 或 cbbd。我写了一个 print 语句来调试并意识到代码认为字符串 aacakdbacaa 和 aacabdkacaa 出于某种原因是等价的。他们显然不是，所以我错过了什么？

class Solution {
    public String longestPalindrome(String s) {
        String longPal = "";
        for(int i = 0; i < s.length(); i++) {
            for(int j = s.length()-1; j >= i; j--) {
                if(s.charAt(i) == s.charAt(j)) {
                    StringBuilder sb = new StringBuilder(s.substring(i, j+1));
                    if(sb.reverse().toString().equals(sb.toString()) 
                       && sb.toString().length() > longPal.length()) {
                        longPal = sb.toString();
                        System.out.println(sb.toString()+" equals "+sb.reverse().toString());
                    }
                    sb.setLength(0);
                }
            }
        }
        return longPal;
    }
}

Answer 1

代码认为 aacakdbacaa 和 aacabdkacaa 不相等。

if语句中条件的第一部分是这样的

sb.reverse().toString().equals(sb.toString())

那么代码（JVM）认为的是这个条件是true。这是为什么？这背后有什么隐藏的知识（因为有一些）？

隐藏的知识部分（不是真的隐藏，在文档中）是StringBuilder reverse 方法改变StringBuilder 的状态（几乎所有SB 方法都这样做）。 reverse 方法还 return StringBuilder 实例本身（其他一些 SB 方法也是如此）。

因此对 sb.reverse() 的调用只是反转 StringBuilder 实例和 return 实例本身的内容（同一个实例！）。实例没有改变，只是它的内部状态改变了。

然后我们对其调用 toString()，return 是当前状态的 String 表示（正如预期的那样）。

然后我们在 returned String 上调用 equals 并将 equals sb.toString() 作为第一个参数的值传入。但是 sb 与之前从 sb.reverse() 编辑的 return 是同一个实例。它的状态在两者之间没有改变，所以我们从对 sb.toString().

的调用中得到相同的 String 表示 returned

这就是为什么

sb.reverse().toString().equals(sb.toString())

是真的。

我们可以写得有点不同，但仍然会得到相同的结果

String s1 = sb.reverse().toString() // sb state changed here when .reverse() was called
String s2 = sb.toString()
s1.equals(s2) // true

或者像这样，很明显

sb.reverse() // sb state changed here
String s1 = sb.toString()
String s2 = sb.toString()
s1.equals(s2) // true

但是，如果我们使用这个顺序，我们会得到不同的结果

String s1 = sb.toString()
sb.reverse() // sb state changed here
String s2 = sb.toString()
s1.equals(s2) // now it depends, true if palindrome, false otherwise!

与

相同

String s1 = sb.toString()
String s2 = sb.reverse().toString()
s1.equals(s2) // true if palindrome, false otherwise!

所以这将是检查回文的正确检查方法

sb.toString().equals(sb.reverse().toString())

奖励：从一个方法调用 return 同一个实例的做法被称为 Fluent interface。

Answer 2

StringBuilder 的 reverse() 方法导致它的字符序列被序列的反向替换，因此 sb.reverse().toString().equals(sb.toString()) 总是结果为真. 声明另一个字符串 String p = sb.toString() 然后用它来比较 sb.reverse().toString().equals(p.toString()) 可能会解决问题。

由于 String / StringBuilder 相等性导致的最长回文边缘案例

Longest Palindrome Edge Case due to String / StringBuilder Equality

java

string

stringbuilder

palindrome