125. 验证回文串

1. 题目

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

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

给你一个字符串 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. 思路

  • 根据题目描述，已知：
    • 只有字母和数字在回文字符串的判断范围内
    • 字母判断时，忽略大小写
  • 设立左右指针l与r，并对其字符串进行循环判断
  • 当l <= r且对应l下标对应的字符与r下标对应的字符不为数字或字符时，进行跳过，跳过指的是当l指针对应的字符不为字符或数字时，将l指针移动到下一位字符
  • 将l指针与r指针对应的字符进行转换，如果对应字符为大写时，则转换成小写，否则将字符原样返回
  • 完成字符统一转换后，对字符进行判断，如果字符不一致，则直接返回结果false
  • 当完成所有字符比对遍历后，返回结果true

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
class Solution {
    public boolean isPalindrome(String s) {
        var l = 0;
        var r = s.length() - 1;

        while (l <= r) {
            while (l <= r && !isAlphabetOrDigital(s.charAt(l))) {
                l++;
            }
            while (l <= r && !isAlphabetOrDigital(s.charAt(r))) {
                r--;
            }

            if (l <= r) {
                var lChar = formatToLowCaseAlaphabet(s.charAt(l));
                var rChar = formatToLowCaseAlaphabet(s.charAt(r));
                if (lChar == rChar) {
                    l++;
                    r--;
                } else {
                    return false;
                }
            }
        }

        return true;
    }

    private boolean isAlphabetOrDigital(char ch) {
        return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || (ch >= '0' && ch <= '9');
    }

    private char formatToLowCaseAlaphabet(char ch) {
        return (ch >= 'A' && ch <= 'Z') ? (char)(ch + 32) : ch;
    }
}

4. 复杂度

  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

image-20230809102957069