Leetcode isPalindrome failing

Question

I wonder how could I make my isPalindrome even faster to pass the bigger strings in leetcode? This is the input my code fails due to exceeding time limit.

import java.util.Stack;
public class Palindrome {
    public boolean isPalindrome(String s){
        Stack<Character> charStack = new Stack<Character>();
        String alphanumericStr="";
        for (int i=0; i<s.length(); i++){
            if (Character.isLetterOrDigit(s.charAt(i))){
                alphanumericStr=alphanumericStr+String.valueOf(s.charAt(i)).toLowerCase();
            }
        }
        System.out.println("str = [" + alphanumericStr + "]");
        if (alphanumericStr.length()==0 || alphanumericStr.length()==1){
            return true;
        }

        if (alphanumericStr.length()%2 == 0){
            if (s.charAt(s.length()/2) != s.charAt((s.length()/2) -1)){
                return false;
            }
        }
        System.out.println( (alphanumericStr.length()/2)-1 );
        for (int i=0; i< (alphanumericStr.length()/2);i++){

                charStack.push(alphanumericStr.charAt(i));

        }

        for (int i=(alphanumericStr.length()/2)+1; i<alphanumericStr.length(); i++){
            if (!charStack.empty()) {
                if (Character.isLetterOrDigit(alphanumericStr.charAt(i))) {
                    if (charStack.pop() != alphanumericStr.charAt(i)) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    public static void main (String[] argc){
        String mimim = "a.";
        Palindrome palindrome=new Palindrome();
        boolean res= palindrome.isPalindrome(mimim);
        System.out.println("result is  = [" + res + "]");
        return;
    }

}

it is failing when the input string is super large! So as a matter of fact I guess I am looking for ways to make it faster! — Mona Jalal, Oct 23 '15 at 07:03
I don't know! The one that it fails is pretty long http://pastebin.com/QUeDgXVQ — Mona Jalal, Oct 23 '15 at 07:07
Instead of using `Stack` why not just compare characters in the string? — Tejas Kale, Oct 23 '15 at 07:08
@mona hope you refer this http://stackoverflow.com/a/4138856/3514144?any special reason for take stack? — Ajay Pandya, Oct 23 '15 at 07:09
Besides using a stack, this would also result in memory (and runtime) problems : `alphanumericStr=alphanumericStr+String.valueOf(s.charAt(i)).toLowerCase();` - you're creating a _new_ string for every character (e.g. "a" + "b" will result in a new object with value "ab", then "ab" + "c" will create "abc" etc.) and thus you'll kill the memory. — Thomas, Oct 23 '15 at 07:25

Thomas · Answer 1 · 2015-10-23T07:17:43.513

This should actually not be that big a problem. Using a stack you might run into memory problems with big strings but I'd say you don't need a stack at all.

Just get the character array and use two indices to check the characters. Start at the front and back of the string, advance each index until you hit an alphanumeric char, check and if both are equal ignoring case advance both (of course you'd "advance" one index backwards starting from the front).

Stop if the the chars are not equal (the string is not a palindrome) or the backwards index is smaller or equal than the forward index.

Edit:

Another maybe not as fast but shorter approach (in terms of code) would be:

//remove all non-alphanumeric chars
String forwardStr = yourString.replaceAll("[^a-zA-Z0-9]","");

//get a reversed version of the strinf
String revStr = new StringBuilder(forwardStr).reverse().toString();

//check equality ignoring case
boolean isPalindrome = forwardStr.equalsIgnoreCase( revStr );

score 0 · Answer 2 · answered Nov 04 '15 at 20:12

My C# solution on leetcode

    var length = s.Length;

    if (length == 0) return false;

    var dic = new Dictionary<char, int>();

    for (var i = 0; i < length; i++)
    {
        if (dic.ContainsKey(s[i]))
        {
            dic[s[i]]++;
            continue;
        }

        dic.Add(s[i], 1);
    }

    var odd = 0;
    foreach (var pv in dic)
    {
        if (odd > 1) return false;
        if (pv.Value % 2 != 0) odd++;
    }

    //code reach here means string IsPpalindorme  
    //but when continue use dictionary build all palindrome permutation, i also had time limit exceeded with string like "aabbhijkkjih" my recursive method seems not right.

score 0 · Answer 3 · answered Mar 26 '17 at 03:43

The time complex of your code is O(N). You can try to use two pointers scan the input string from both sides to the middle at the same time. So the time complex will go down to the O(logN). Here is my sample JAVA code.

public class Palindrome {
    public boolean isPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }

        int front = 0;
        int end = s.length() - 1;
        while (front < end) {
            while (front < s.length() && !isvalid(s.charAt(front))){//check border
                front++;
            }

            if (front == s.length()) { // for emtpy string   
                return true; 
            }           

            while (end >= 0 && ! isvalid(s.charAt(end))) {//check border
                end--;
            }

            if (Character.toLowerCase(s.charAt(front)) != Character.toLowerCase(s.charAt(end))) {
                break;
            } else {
                front++;
                end--;
            }
        }

        return end <= front; 
    }

    //check if the character is a letter or a digit
    private boolean isvalid (char c) {
        return Character.isLetter(c) || Character.isDigit(c);
    }
}

score 0 · Answer 4 · answered Jun 08 '18 at 11:14

The Big-O of your algorithm is just O(n), it is just you used too many for loops so that it wastes your time a lot.

If you just want to find better solution for leetcode problems, just go to discuss pages, they do have lots of good answers.

If you still don't get their ideas, you can check back here on StackOverFlow

score -1 · Answer 5 · answered Apr 02 '19 at 01:58

-1

public boolean isPalindrome(String s) {
    char [] chars = s.toLowerCase().replaceAll("[^a-z0-9]", "").toCharArray();
    for (int i=0; i< chars.length; i++) {
        if (!Character.isLetterOrDigit(chars[i])){
            continue;
        }
        if (chars[i] != chars[chars.length-1 -i]) {
            return false;
        }
    }

    return true;

}

answered Apr 02 '19 at 01:58

Naeem

1
3

1

Short answers of just code are considered low quality. Please explain the key points of your code and how it differs from the established answers. – Simon.S.A. Apr 02 '19 at 02:20

Leetcode isPalindrome failing

5 Answers5