Leetcode problem 125. Valid Palindrome：

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.

I appended each character into two linked lists, one forwards and one backwards, and compared them. However, I did not pass the time limit. The Leetcode's solution used a StringBuilder and reversed it. I heard that StringBuilder is implemented similar to a linked list. I have no idea why my code is much slower than the solution. I would appreciate any feedback or insights on this topic. Thank you in advance.

My code:

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 Solution:

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);
  }
}

CodePudding user response：

If you look at how reverse() method is implemented in AbstractStringBuilder you can see that it uses array to store characters. It is the main difference between StringBuilder and your solution. forward.get(i) and backward.get(i) have O(n) complexity, when value[j] has O(1).

Java 8 implementation:

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;
}

CodePudding user response：

Actually, Leetcode solution does not seem to be the best and StringBuilder::reverse method does not have to be used at all to detect a palindrome, because it is possible to check the characters from the start and end of the string to its center and as soon as unmatching pair is found the string is NOT a palindrome.

Also conversion of StringBuilder to direct and reversed strings is redundant.

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;
  }
}

Similar solution using Stream API and a regexp to clean out non-letter and non-digit characters (in 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));
}