为什么StringBuilder.reverse比追加到链表更快

Question

Leetcode问题125。有效回文：

Given a string s, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

我将每个字符添加到两个链表中，一个向前，一个向后，并对它们进行比较。但是，我没有超过时间限制。Leetcode的解决方案使用了StringBuilder，并将其颠倒过来。我听说StringBuilder的实现类似于链表。我不知道为什么我的代码比解决方案慢得多。如果有任何关于这个话题的反馈或见解，我将非常感激。提前谢谢你。

我的代码：

class Solution {
    public boolean isPalindrome(String s) {
        LinkedList<Character> forward = new LinkedList<Character>();
        LinkedList<Character> backward = new LinkedList<Character>();
        for(int i = 0 ; i < s.length() ; i++){
            char ch = s.charAt(i);
            if(Character.isLetterOrDigit(ch)){
                if(Character.isLetter(ch)) ch = Character.toLowerCase(ch);
                forward.addLast(ch);
                backward.addFirst(ch);
            }
        }
        for(int i = 0 ; i < forward.size() ; i++){
            if(forward.get(i) != backward.get(i)) return false;
        }
        return true;
    }
}

Leetcode解决方案：

class Solution {
  public boolean isPalindrome(String s) {
    StringBuilder builder = new StringBuilder();

    for (char ch : s.toCharArray()) {
      if (Character.isLetterOrDigit(ch)) {
        builder.append(Character.toLowerCase(ch));
      }
    }

    String filteredString = builder.toString();
    String reversedString = builder.reverse().toString();

    return filteredString.equals(reversedString);
  }
}

Answer 1

如果查看AbstractStringBuilder中的reverse()方法是如何实现的，就会发现它使用数组来存储字符。这是StringBuilder和您的解决方案之间的主要区别。当forward.get(i)和backward.get(i)的复杂度为O(1)时，value[j]的复杂度为O(n)。

Java 8实现：

public AbstractStringBuilder reverse() {
    boolean hasSurrogates = false;
    int n = count - 1;
    for (int j = (n-1) >> 1; j >= 0; j--) {
        int k = n - j;
        char cj = value[j];
        char ck = value[k];
        value[j] = ck;
        value[k] = cj;
        if (Character.isSurrogate(cj) ||
            Character.isSurrogate(ck)) {
            hasSurrogates = true;
        }
    }
    if (hasSurrogates) {
        reverseAllValidSurrogatePairs();
    }
    return this;
}

Answer 2

实际上，Leetcode解决方案似乎并不是最好的，StringBuilder::reverse方法根本不需要使用来检测回文，因为它可以检查字符串的开始和结束到其中心的字符，并且一旦发现不匹配的对，该字符串就不是回文。

此外，将StringBuilder转换为正向和反向字符串也是多余的。

class Solution {
  public boolean isPalindrome(String s) {
      StringBuilder builder = new StringBuilder(s.length());

      for (char ch : s.toCharArray()) {
          if (Character.isLetterOrDigit(ch)) {
              builder.append(Character.toLowerCase(ch));
          }
      }
      for (int i = 0, n = builder.length(), m = n / 2; i < m; i++) {
          if (builder.charAt(i) != builder.charAt(n - i - 1)) {
              return false;
          }
      }
      return true;
  }
}

使用Stream API和regexp清除非字母和非数字字符(在Unicode中)的类似解决方案：

public static boolean isPalindrome(String s) {
    String str = s.replaceAll("[^\\p{L}\\p{N}]", "").toLowerCase();
    final int n = str.length();
    return IntStream.range(0, n / 2)
                .allMatch(i -> str.charAt(i) == str.charAt(n - 1 - i));
}