Leetcode Valid Palindrome Question Problem Debugging

Question

I'm struggling to understand what's wrong with my code for this Leetcode problem.

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

Right now, I am passing 108/476 cases, and I am failing this test: "A man, a plan, a canal: Panama".

Here is my code, please help me identify the problem!

class Solution {
public boolean isPalindrome(String s) {

    if (s.isEmpty()) return true;

    s.replaceAll("\\s+","");

    int i = 0;
    int j = s.length() - 1;

    while (i <= j) {

        if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) {

            return false;

        }

        i++;
        j--;

    }

    return true;

}
}

The problem in your code is that you don't take special characters (other than spaces) into account. Basically, you should move `i` to the next **letter** (not character) and `j` to the previous one. — Olivier Grégoire, May 18 '20 at 15:07
Also [How to replace a substring of a string](https://stackoverflow.com/q/16702357/525036) (duplicate of the previous one) — Didier L, May 18 '20 at 15:10
Note that if you want to pass the test, you will also have to change your regular expression to cover more than whitespace characters. Non-alphanumeric characters are represented with `\W`. — Didier L, May 18 '20 at 15:14

Olivier Grégoire · Answer 1 · 2020-05-18T15:55:52.733

Your replaceAll method is incorrect

Your replaceAll method currently only removes spaces. It should remove all the special characters and keep only letters. If we use the regex way like you do, this is (one of) the best regex to use:

s = s.replaceAll("[^a-zA-Z]+","");

You could be tempted to use the \W (or [^\w]) instead, but this latest regex matches [a-zA-Z0-9_], including digits and the underscore character. Is this what you want? then go and use \W instead. If not, stick to [^a-zA-Z].

If you want to match all the letters, no matter the language, use the following:

s = s.replace("\\P{L}", "");

Note that you could shorten drastically your code like this, although it's definitely not the fastest:

class Solution {
  public boolean isPalindrome(String s) {
    s = s.replaceAll("\\P{L}", "");
    return new StringBuilder(s).reverse().toString().equalsIgnoreCase(s);
  }
}

score 2 · Answer 2 · answered May 18 '20 at 15:11

2

Your regex is invalid. Try this:

s = s.replaceAll("[\\W]+", "");

\W is used for anything that is not alphanumeric.

answered May 18 '20 at 15:11

Aniket Sahrawat

12,410
3
41
67

score 1 · Answer 3 · answered May 18 '20 at 15:12

1

By s.replaceAll("\\s+",""); you are only removing the spaces but you also have to remove anything except alphanumeric characters such as punctuation, in this case ,.

answered May 18 '20 at 15:12

Sajib

404
3
15

Leetcode Valid Palindrome Question Problem Debugging

3 Answers3

Your replaceAll method is incorrect