125. 验证回文串

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

说明：本题中，我们将空字符串定义为有效的回文串。

示例 1:

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

示例 2:

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

提示：

  • 1 <= s.length <= 2 * 105
  • 字符串 s 由 ASCII 字符组成

题解：

解法1：反转

将字符串中的有效字符构建为一个新的字符串，将其反转，与原有字符串进行比较，若相等，则为回文串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//使用StringBuffer是为了方便调用API
StringBuffer sgood = new StringBuffer();
int length = s.length();

for (int i = 0; i < length; i++) {
    char c = s.charAt(i);
    //Character.isLetterOrDigit(c)表示如果字符是字母或数字，则返回布尔值为true，否则返回为false
    if (Character.isLetterOrDigit(c)) {
        //Character.toLowerCase(c)表示把字符转换为小写
        sgood.append(Character.toLowerCase(c));
    }
}

StringBuffer sgoodRev = new StringBuffer(sgood).reverse();
//验证字符串反转完是否和原字符串相同
return sgoodRev.toString().equals(sgood.toString());
  • 时间复杂度：O(N)
  • 空间复杂度：O(N)
解法2：双指针

和解法一一样，首先将字符串中的有效字符取出，然后使用双指针进行前后比较向中间移动，直到两指针相遇。

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
public boolean isPalindrome(String s) {
    //空串也是回文串
    if(s.length() == 0){
        return true;
    }
    
    
    //使用StringBuffer来构建出只含有字母和数字的字符串
    StringBuffer sgood = new StringBuffer();
    
    int len = s.length();
    
    for(int i = 0;i < len;i++){
        char c = s.charAt(i);
        //如果当前字符是字母或者数字，就将其追加到StringBuffer上
        if(Character.isLetterOrDigit(c)){
            //因为题目说了忽略大小写，我们就索性直接全部转为小写
            sgood.append(Character.toLowerCase(c));
        }
    }
    
    //到此，新字符串sgood构建完成，但是这个的sgood和原来的s的长度可能是不相同的，要注意
    int length = sgood.length();
    
    //使用双指针判断是否回文
    int l = 0, r = length -1;
    
    while(l < r){
        //两指针指向的字符不相同，则证明不是回文串，直接返回false
        if(sgood.charAt(l) != sgood.charAt(r)){
            return false;
        }
        //否则，移动双指针
        l++;
        r--;
    }
    
    return true;
    
}
  • 时间复杂度：O(N)
  • 空间复杂度：O(N)