125. Valid Palindrome判断有效的有符号的回文串

［抄题］：

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

[暴力解法]：

时间分析：

空间分析：

[优化后]：

时间分析：

空间分析：

［奇葩输出条件］：

用cHead cTail 存头尾字母，不用每次都临时转换

［奇葩corner case］：

空字符串是具体的实例对象，所以用isempty()而不是null
此题中大小写不敏感，所以需要都转换为小写

［思维问题］：

不知道符号怎么处理：Character.isLetterOrDigit

［一句话思路］：

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

此题特殊：while里面嵌套if else if，一次只操作一位，防止指针没到位就判断对称了.chead ctail属于因变量，都要在循环体内随即变化，下次注意
一对字母不管是否对称，都要继续head++ tail-- 促进下一步继续进行，要理解到位

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

while里面嵌套if else if，一次只操作一位，防止指针没到位就判断对称了.chead ctail属于因变量，都要在循环体内随即变化，下次注意

［复杂度］：Time complexity: O(n) Space complexity: O(1)

［英文数据结构或算法，为什么不用别的数据结构或算法］：

［关键模板化代码］：

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

[代码风格] ：

public class Solution {
    /**
     * @param s: A string
     * @return: Whether the string is a valid palindrome
     */
    public boolean isPalindrome(String s) {
        //cc
        if (s.isEmpty()) {
            return true;
        }
        
        //define
        int head = 0, tail = s.length() - 1;
        
        while (head < tail) {
            char cHead = s.charAt(head), cTail = s.charAt(tail);
            //judge:punction or not
            if (!Character.isLetterOrDigit(cHead)) {
                head++;
            }else if (!Character.isLetterOrDigit(cTail)) {
                tail--;
            }else {
                //tolowercase and judge
                if (Character.toLowerCase(cHead) != Character.toLowerCase(cTail)) {
                    return false;
                }
                //continue 
                head++;
                tail--;
            }
        }
    
        //return
        return true;
    }
}

View Code