给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

解一：
首先想到既然只考虑字母和数字字符，那么我们可以先过滤下参数，然后将其反转得到新的字符串，再和过滤后的字符串进行equalsIgnore看其是否相同：

public boolean isPalindrome(String s) {

        if(s == null){

            return false;

        }

        if(s.equals("")){

            return true;

        }

        String filterStr = filterStr(s);

        String reversedStr = reverseStr(filterStr);

        return filterStr.equalsIgnoreCase(reversedStr);

    }

    private String reverseStr(String filterStr) {

        return new StringBuilder(filterStr).reverse().toString();

    }

    private String filterStr(String s) {

        return s.replaceAll("[^a-zA-Z0-9]", "");

    }

没问题，此解法只设计字符串的反转和判断，在过滤和反转时分别创建了新的字符串，所以平均时间复杂度为O(n)，空间复杂度为O(n)。执行测试，虽然通过了，但是发现其执行耗时很高：

leetcode.png

我们用了正则，耗时当然很高。

解法二：
我们看下leetcode官方提供的解法：直接在原字符s上使用双指针（这个双指针是个神奇的东西~），在移动任意一个指针时，需要不断地向另一指针的方向移动，直到遇到一个字母或数字字符，或者两指针重合为止。

public boolean isPalindrome2(String s) {
        if (s == null) {
            return false;
        }
        if (s.equals("")) {
            return true;
        }
        int len = s.length();
        int left = 0, right = len - 1;
        while (left < right) {
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            }
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                right--;
            }
            if (left < right) {
                if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                    return false;
                }
                left++;
                right--;
            }
        }
        return true;
    }

再执行下测试：

leetcode2.png

因为没有额外的字符串开辟，只是用到了两个指针变量，所以空间复杂度为O(1)，字符串长度为n需要遍历n/2次即可，所以时间复杂度为O(n)