125. 验证回文串(简单)

Posted on In Views:

1，问题描述

125. 验证回文串

难度：简单

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

示例 1：

1
2
3
输入: s = "A man, a plan, a canal: Panama"
输出：true
解释："amanaplanacanalpanama" 是回文串。

示例 2：

1
2
3
输入：s = "race a car"
输出：false
解释："raceacar" 不是回文串。

示例 3：

1
2
3
4
输入：s = " "
输出：true
解释：在移除非字母数字字符之后，s 是一个空字符串 "" 。
由于空字符串正着反着读都一样，所以是回文串。

提示：

  • 1 <= s.length <= 2 * 105
  • s 仅由可打印的 ASCII 字符组成

2，初步思考

​ 直接使用双指针，由两边向中间去判断，这个是解决回文问题的固定套路

3，代码处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
public class _125验证回文串 {

    // 解法：正则表达式替换字符
    public boolean isPalindrome_regular(String s) {
        StringBuilder stringBuilder = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (Character.isLetterOrDigit(c)) {
                stringBuilder.append(Character.toLowerCase(c));
            }
        }

        int left = 0, right = stringBuilder.length() - 1;

        while (left <= right) {
            if (stringBuilder.charAt(left) != stringBuilder.charAt(right)) return false;
            left++;
            right--;
        }
        return true;
    }

    public boolean isPalindrome_gov(String s) {
        char[] charArray = s.toCharArray();
        int left = 0, right = charArray.length - 1;
        while (left <= right) {
            while (left < right && !Character.isLetterOrDigit(charArray[left])) {
                left++;
            }
            while (left < right && !Character.isLetterOrDigit(charArray[right])) {
                right--;
            }
            if (!(Character.toLowerCase(charArray[left]) == Character.toLowerCase(charArray[right]))) return false;
            left++;
            right--;
        }
        return true;
    }


    static int aInt = 'a';
    static int zInt = 'z';
    static int AInt = 'A';
    static int ZInt = 'Z';
    static int zeroInt = '0';
    static int nineInt = '9';
    static int diff = 'a' - 'A';

    // 解法：双指针
    public boolean isPalindrome(String s) {
        char[] charArray = s.toCharArray();
        int left = 0, right = charArray.length - 1;
        while (left <= right) {
            while (left < right && !isValidaChar(charArray[left])) {
                left++;
            }
            while (left < right && !isValidaChar(charArray[right])) {
                right--;
            }
            if (!compareChar(charArray[left], charArray[right])) return false;
            left++;
            right--;
        }
        return true;
    }

    private boolean isValidaChar(char c) {
        return (c >= AInt && c <= ZInt) || (c >= aInt && c <= zInt) || (c >= zeroInt && c <= nineInt);
    }

    private boolean compareChar(char a, char b) {// a, b都是字母
        if (a == b) return true;
        if (a <= ZInt && a >= AInt) {
            return a + diff == b;
        } else if (a >= aInt && a <= zInt) {
            return a - diff == b;
        }
        return false;
    }

    public static void main(String[] args) {
        _125验证回文串 isPalindrome = new _125验证回文串();
        System.out.println(isPalindrome.isPalindrome("0P"));
        System.out.println(isPalindrome.isPalindrome("aA"));
        System.out.println(isPalindrome.isPalindrome(" "));
        System.out.println(isPalindrome.isPalindrome("race a car"));
        System.out.println(isPalindrome.isPalindrome("A man, a plan, a canal: Panama"));
    }
}