Thursday, December 8, 2016

Leetcode/各大家 -- 125.Valid Palindrome

125. Valid Palindrome
check if a string is valid palindrome without modifying str
Link: https://leetcode.com/problems/valid-palindrome/


思路:use two pointer, i from start j from end, convert char to uppercase & watch cases symbol,
关键词: char的操作(Character.toUpperCase & Character.isLetterOrDigit(c))
Time & Space complexity: O(n) time O(1) space

public class Solution {
    public boolean isPalindrome(String s) {
        int i=0;
        int j = s.length() -1;
        while(i<j){
            if(s.charAt(i) != s.charAt(j)){
                char a = Character.toUpperCase(s.charAt(i));
                char b = Character.toUpperCase(s.charAt(j));

                if( a == b ){//A?a
                    i++;
                    j--;
                }else{
                    if(!Character.isLetterOrDigit(a)){//char is not capital letter or number
                        i++;
                    }else if(!Character.isLetterOrDigit(b)){
                        j--;
                    }else{
                        return false;//letters & number not mactch
                    }
                }
            }else{
                i++;
                j--;
            }
        }
        return true;
    }
}

No comments:

Post a Comment