7ms solution with O(1) of S(n)


  • 0
    J

    If the string is empty or length is 0 , return true, according to the hint.
    Here I use two pointers to iterate each characters from head and tail respectively and check whether equals. Be caution with the 'alphanumeric' word and ignore cases . T(n) = O(n), S(n) = O(1), beating 88% submission, almost good.

    Option: process the char array at first to remove nonalphanumeric word, then use two pointers to compare each char will get better performance. However it will need auxiliary storage with O(n).

    public class Solution {
         public boolean isPalindrome(String s) {
            if (null == s || s.equals("") ||s.length() == 0){
                return true;
            }
            int l = 0;
            int r = s.length() - 1;
            while (l < r){
                while (l<r && !isAlpha(s.charAt(l))){
                    l++;
                }
                while(l<r && !isAlpha(s.charAt(r))){
                    r--;
                }
                if (equals(s.charAt(l), s.charAt(r))){
                    l++;
                    r--;
                } else {
                    return false;
                }
            }
    
            return true;
        }
        public static boolean isChar(char c){
            if (('A' <= c && c <= 'Z') || ('a' <= c && c <='z')){
                return true;
            } else {
                return false;
            }
        }
        public static boolean isNum(char c){
            if ('0' <= c && c <= '9'){
                return true;
            } else {
                return false;
            }
        }
        public static boolean isAlpha(char c){
            return isNum(c) || isChar(c);
        }
        public static boolean equals(char c, char d){
            if (c==d || (Math.abs(c-d) == 32 && isChar(c) && isChar(d))){
                return true;
            } else {
                return false;
            }
        }
    
    }

Log in to reply
 

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