LeetCode题解-125.valid-palindrome

125.valid-palindrome

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。

示例 1:
输入: “A man, a plan, a canal: Panama”
输出: true

示例 2:
输入: “race a car”
输出: false

题解:
本题很明显使用双指针就可以解决问题，非常直观，判断处使用了库函数。

class Solution {
    public boolean isPalindrome(String s) {
        // 设置头尾指针
        int i = 0;
        int j = s.length() - 1;
        while(true) {
            if(i >= j) {
                return true;
            }
            // 判断是否为字母或者字符串
            if(!Character.isLetterOrDigit(s.charAt(i))) {
                i++; 
            } else if(!Character.isLetterOrDigit(s.charAt(j))) {
                j--;
            } else if(Character.toLowerCase(s.charAt(i)) == Character.toLowerCase(s.charAt(j))) {
                i++;
                j--;
            } else {
                return false;
            }
        }
    }
}

上述算法时间复杂度为O(n)（一次遍历），空间复杂度为O(1)(开辟变量存储空间)
总结：能使用双指针的题目算法时间效率不差，而且代码简单易写。