public class Solution {
    /**
     * @param s: 一个字符串
     * @return: 该字符串是否有有效回文串
     */
    public boolean isPalindrome(String s) {
        if (s == null) {
            return false;
        }
        // 双指针
        int left = 0, right = s.length() - 1;
        while (left < right) {
            // 左指针向右移动, 一直移动, 直到遇到一个合法的字符, 即字母或数字
            while (left < right && !isValid(s.charAt(left))) {
                left ++;
            }
            // 右指针向左移动, 一直移动, 直到遇到一个合法的字符, 即字母或数字
            while (left < right && !isValid(s.charAt(right))) {
                right --;
            }
            // 对比两个指针指向的字符, 如果不相等, 则说明该字符串不是有效回文串
            if (left < right && !isEqual(s.charAt(left), s.charAt(right))) {
                return false;
            }
            // 两指针相向移动
            left++;
            right--;
        }
        return true;
    }
    /**
     * 判定字符串是否是字母或数字
     * @param c 被判定的字符串
     * @return 是否是字母或数字
     */
    private boolean isValid(char c) {
        return Character.isLetter(c) || Character.isDigit(c);
    }
    /**
     * 对比两个字符是否相等, 忽略大小写, 先将字符转为小写字母, 然后再对比
     * @param a 对比的字符一
     * @param b 对比的字符二
     * @return 字符转为小写字母后, 是否相等
     */
    private boolean isEqual(char a, char b) {
        return Character.toLowerCase(a) == Character.toLowerCase(b);
    }
}
class Main{
    public static void main(String[] args) {
        boolean isPalindrome = new Solution().isPalindrome("A man, a plan, a canal: Panama");
        System.out.println(isPalindrome);
    }
}