I am having an issue with a particular leetcode problem called Valid Palindrome. My code works for all test cases except the last test case 479/480.

In this test case a 106890 length string is passed in but my code takes too long to solve it.

I decided to try take a different approach and use the StringBuilder class to reverse the string and then simply use reversedString.equals(originalString) to compare whether they are a palindrome. This approach solves the question and passes all testcases

Why doesn't my two pointer approach work? Why does it fail on the last test case?

Here is my solution (Two Pointer)

class Solution {
    public static boolean isPalindrome(String s) {
        String fixedString = "";
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c) || Character.isLetter(c)) {
                fixedString  = c;
            }
        }
        fixedString = fixedString.toLowerCase();
        int i = 0;
        int j = fixedString.length() - 1;
        System.out.println(fixedString.toCharArray());
        while (i <= j) {
            if (fixedString.toCharArray()[i] != fixedString.toCharArray()[j]) {
                return false;
            }
            i  = 1;
            j -= 1;
        }
        return true;
    }
}

Here is my second solution using StringBuilder.

public class Valid_Palindrome {

    public static void main(String args[]){
        System.out.println(isPalindrome("A man, a plan, a canal: Panama"));
    }

    public static boolean isPalindrome(String s) {
        String fixedString = "";
        for(char c : s.toCharArray()){
            if(Character.isDigit(c) || Character.isLetter(c)){
                fixedString  = c;
            }
        }
        fixedString = fixedString.toLowerCase();
        StringBuilder sb = new StringBuilder(fixedString);
        sb = sb.reverse();
        System.out.println(sb);
        return sb.toString().equals(fixedString);
    }
}

Technically speaking, isn't the second solution supposed to be much slower since it is using StringBuilder?

How do I optimize my first solution?

Here is the input string that is passed in my leetcode.

CodePudding user response：

It is generally slow to perform string concatenation in a loop. Use a StringBuilder instead in the first loop to create the filtered string.

StringBuilder sb = new StringBuilder(s.length());
for (int i = 0; i < s.length(); i  ) {
    char c = s.charAt(i);
    if (Character.isLetterOrDigit(c))
        sb.append(Character.toLowerCase(c));
}
for (int i = 0, j = sb.length() - 1; i < j; i  , j--)
    if (sb.charAt(i) != sb.charAt(j))
        return false;
return true;

CodePudding user response：

Don't build or reverse or do anything with the string, except iterate over half its characters.

In pseudo code:

• Loop over the first half of the characters
• For the ith character, compare it with the (length - i - 1)th character
• If different, return false
• If loop ends, return true

CodePudding user response：

There are a couple of statements in your code that are probably slowing it down.

1. fixedString = c;
   This creates a new StringBuilder object. The contents of fixedString are copied to it. Then the character (c) is appended. Then the StringBuilder is converted to a String and that String is assigned to variable fixedString.
2. if (fixedString.toCharArray()[i] != fixedString.toCharArray()[j])
   Method toCharArray creates a new char[] and copies the contents of the String to it.

I suggest that you create the char[] once only and work with it. Of-course you need to remove the non-letters and non-digits from the original string as well as convert to lower case.

Here is my rewrite of your [two pointer] solution.
(Note that I assume that a null or empty string is not a palindrome.)

public static boolean isPalindrome(String s) {
    if (s != null && !s.isEmpty()) {
        char[] chars = s.toCharArray();
        char[] temp = new char[chars.length];
        int count = 0;
        for (char c : chars) {
            if (Character.isDigit(c) || Character.isLetter(c)) {
                temp[count  ] = Character.toLowerCase(c);
            }
        }
        char[] letters = new char[count];
        System.arraycopy(temp, 0, letters, 0, count);
        int i = 0;
        int j = count - 1;
        System.out.println(letters);
        while (i <= j) {
            if (letters[i] != letters[j]) {
                return false;
            }
            i  ;
            j--;
        }
        return true;
    }
    return false;
}