first write-up: valid palidrome 7ms solution, java

  • 0

    The logic is simple. Palindrome has identical letters when compared outside-in from a string. When traversing the string, we skip non-alphanumeric characters by checking if the characters' ASCII values fall outside the range of that of a-z and 0 to 9. The skip can be achieved by moving the string index by i++ or j--, or both, depending on where these non-alphanumeric characters appear in the string.
    We do our actual character comparison only after we check that both of them are alphanumeric characters. Return false right away if they do not match. Otherwise, continue until j=i, which must be equal as we are comparing a character with itself.

    Worse case running time is O(length of string), where all characters are non-alphanumeric except one at the very beginning or at the end. Best case running time is O(string length/2), as with each loop, i++ and j--.

    class Solution {
        public boolean isPalindrome(String s) {
            if(s.isEmpty()) return true; 	
            int i = 0;
            int j = s.length()-1;
                char a = Character.toLowerCase(s.charAt(i));
                char b = Character.toLowerCase(s.charAt(j));
    			boolean isCharASymbol = !(a>='a' && a<='z') && !(a>='0' && a<='9');
    			boolean isCharBSymbol = !(b>='a' && b<='z') && !(b>='0' && b<='9'); 
    				i++; continue; 
    				j--; continue; 
    			if(a != b) return false; 
    			i++; j--; 
            return true;    //j==i

Log in to reply

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