leetcode解題：(Easy) 125. Valid Palindrome

題目：https://leetcode.com/problems/valid-palindrome/

描述：給定一個字串，辨識該字串是否為回文，如果該字串在將所有字母轉為小寫後並移除其中的非字母數字(non-alphanumeric)的字元後，正寫反寫都一樣的話即為回文

解題思路：用two pointer，先將字串的字母轉為小寫，2個pointer分別從字串頭尾開始向中間移動比較2個pointer位置的字元是否相同，遇到非字母數字就跳過

程式碼：

class Solution {
    public boolean isPalindrome(String s) {
        s = s.toLowerCase();

        for(int i = 0, j = s.length()-1; i <= j;) {
            if(s.charAt(i) < '0' || s.charAt(i) > 'z') i++;
            else if(s.charAt(i) < 'a' && s.charAt(i) > '9') i++;
            else if(s.charAt(j) < '0' || s.charAt(j) > 'z') j--;
            else if(s.charAt(j) < 'a' && s.charAt(j) > '9') j--;
            else {
                if(s.charAt(i) != s.charAt(j)) return false;
                i++;
                j--;
            }
        }

        return true;
    }
}

時間複雜度：O(n)
空間複雜度：只用2個pointer的理想狀況是O(1)，但我的程式碼偷懶使用toLowerCase()有產生新字串，所以應該會是O(n)

tags: leetcode easy two pointer