Accepted pretty Java solution(271ms)


  • 71
    O
    public class Solution {
        public boolean isPalindrome(String s) {
            if (s.isEmpty()) {
            	return true;
            }
            int head = 0, tail = s.length() - 1;
            char cHead, cTail;
            while(head <= tail) {
            	cHead = s.charAt(head);
            	cTail = s.charAt(tail);
            	if (!Character.isLetterOrDigit(cHead)) {
            		head++;
            	} else if(!Character.isLetterOrDigit(cTail)) {
            		tail--;
            	} else {
            		if (Character.toLowerCase(cHead) != Character.toLowerCase(cTail)) {
            			return false;
            		}
            		head++;
            		tail--;
            	}
            }
            
            return true;
        }
    }

  • 0
    S

    I am wondering why this Character operation approach works faster than normal Regex one?


  • 0
    Y

    Regex one will create a new string if you call replaceAll() or something like that, which is slow and used O(N) space, I would not recommend a way to use regex


  • 11
    S

    I don't see any reason to enter the while loop when head = tail.
    while(head < tail) should be enough.


  • 0
    V

    Should be while(head < tail)


  • 0
    B

    if cHead or cTail is digit, what will be the result of toLowerCase?


  • 2
    S
    public class Solution {
    public boolean isPalindrome(String s) {
        if(s == null){
            return false;
        }
        if(s.length() <= 1){
            return true;
        }
        int low = 0;
        int high = s.length()-1;
        while(low<high){
            if(shouldIgnore(s.charAt(low))){
                low++;
                continue;
            }
            if(shouldIgnore(s.charAt(high))){
                high--;
                continue;
            }
            if(!isSameLetter(s.charAt(low), s.charAt(high))){
                return false;
            }
            low++;
            high--;
        }
        return true;
    }
    
    public boolean isLetter(char x){
        if(x>=65 && x<=90){
            return true;
        }
        if(x>=97 && x<=122){
            return true;
        }
        return false;
    }
    
    public boolean isSameLetter(char x, char y){
        if(isLetter(x) && isLetter(y)){
            if(x == y || x == y+32 || x+32 == y){
                return true;
            }
        }else{
            if(x == y){
                return true;
            }
        }
        return false;
    }
    
    public boolean shouldIgnore(char x){
        if(x >= 48 && x <= 57){
            return false;
        }
        return !isLetter(x);
    }
    

    }


  • 1
    B

    Making the call toLowerCase at the moment of comparison is far more clever than converting the entire string to lower case at the beginning, as I was doing haphazardly.


  • 0
    O

    @BroLegend it will be an error


  • 0
    S

    @BroLegend toLowerCase() returns the character itself if it does not have a lower case.


  • 2
    L

    13ms Accepted C++ code.

    class Solution {
    public:
        bool isPalindrome(string s) {
            int n = s.size();
            int i = 0, j = n-1;
            while (i < j) {
                while (!isalnum(s[i]) && i < j) i++;
                if (i == j) break;
                while (!isalnum(s[j]) && i < j) j--;
                if (i==j) break;
                char si = s[i], sj=s[j];
                si = isalpha(si) ? tolower(si) : si;
                sj = isalpha(sj) ? tolower(sj) : sj;
                if (si != sj) return false;
                i++;
                j--;
            }
            return true;
        }
    };
    

  • 8

    Thanks for sharing! But I think it could be more concise.

        public boolean isPalindrome(String s) {
            char[] c = s.toCharArray();
            for (int i = 0, j = c.length - 1; i < j; ) {
                if (!Character.isLetterOrDigit(c[i])) i++;
                else if (!Character.isLetterOrDigit(c[j])) j--;
                else if (Character.toLowerCase(c[i++]) != Character.toLowerCase(c[j--])) 
                    return false;
            }
            return true;
        }
    

  • 0

    Could be a little bit faster:

    public class Solution {
        public boolean isPalindrome(String s) {
            s = s.trim().toLowerCase(); 
            if(s.length() == 0) return true; 
            int p1 = 0; 
            int p2 = s.length()-1; 
            
            while(p1 < p2){
                while(!alphanumeric(s.charAt(p1)) && p1 < s.length() - 1) p1++;
                while(!alphanumeric(s.charAt(p2)) && p2 >0) p2--;
                if(p1 >= p2) return true; 
                if(s.charAt(p1) == s.charAt(p2)){
                    p1++; p2--; 
                }else return false; 
            }
            return true; 
        }
        
        private boolean alphanumeric(char c){
            if( c - '0' >= 0 && c - '0' <= 9 ) return true; 
            if( c - 'a' >= 0 && c - 'z' <= 0 ) return true; 
            return false; 
        }
    }
    

  • 1
    A

    Nice!
    Taking inspiration from your answer I also coded the solution.
    You can actually get rid of extra space in terms of char head; char tail;
    Have a look at my solution. It looks cleaner and smaller. Easy to Understand.

    public class Solution {
        public static boolean isPalindrome(String s) {
    		if(s==null || s.trim().length()==0)	return true;
    		int i=0, j=s.length()-1;		
    		
    		while(i<=j){			
    		  while(i<j && !Character.isLetterOrDigit(s.charAt(i)))	i++;
    		  while(i<j && !Character.isLetterOrDigit(s.charAt(j)))	j--;
    			if( Character.toLowerCase(s.charAt(i))!=Character.toLowerCase(s.charAt(j)) )	return false;
    			i++; j--;
    		}
    		return true;
        }
    }
    

    Surprisingly, not many people know that to check if the character is alphanumeric, Character class has a method called Character.isLetterOrDigit(c).


  • 0
    W

    so this solution will give runtime error?


  • 0
    J

    I think there are testcases added which makes the above algorithm non-working!


  • 1
    L

    This works. (10ms)

    public class Solution {
        public boolean isPalindrome(String s) {
            s = s.toLowerCase();
            int l = 0, r = s.length()-1;
            while(l < r)
                if((s.charAt(l) > 'z' || s.charAt(l) < 'a') && (s.charAt(l) > '9' || s.charAt(l) < '0')) l++;
                else if((s.charAt(r) > 'z' || s.charAt(r) < 'a') && (s.charAt(r) > '9' || s.charAt(r) < '0')) r--;
                else if(s.charAt(l++) != s.charAt(r--)) return false;
            return true;
        }
    }

  • 0
    J
    This post is deleted!

  • 0
    J

    @luckman It worked! Thank you!


  • 4

    Ugly, but works:

    boolean isPalindrome(String s) {
      s = s.toLowerCase().replaceAll("\\W+", "");
      return s.equals(new StringBuilder(s).reverse().toString());
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.