125. 验证回文串

Posted on | In
Words count in article: 374 | Reading time ≈ 1

题目

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

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

示例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 字符组成

解法

解法一：

双指针

首尾遍历，遇到非字符的跳过，然后判断是否相等

Java

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
public boolean isPalindrome(String s) {
        if(s == null || s.length() == 0) {
            return true;
        }
            
        int l = 0;
        int r = s.length()-1;
        while(l < r) {
            if(!isValid(s.charAt(l))) {
                l++;
                continue;
            }
            if(!isValid(s.charAt(r))) {
                r--;
                continue;
            }
            if(!isSame(s.charAt(l), s.charAt(r))) {
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
    
    private boolean isValid(char c) {
        if(c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z' || c >= '0' && c <= '9') {
            return true;
        }
        return false;
    }
    
    private boolean isSame(char c1, char c2) {
        if(c1 >= 'A' && c1 <= 'Z') {
            c1 = (char)(c1 - 'A' + 'a');
        }
        
        if(c2 >= 'A' && c2 <= 'Z') {
            c2 = (char)(c2 - 'A' + 'a');
        }
        return c1 == c2;
    }

解法二：

库函数

1
2
3
4
5
6
7
8
public boolean isPalindrome(String s) {
        String str = s.toLowerCase();
        StringBuilder sb = new StringBuilder();
        for(char c : str.toCharArray()){
            if(Character.isLetterOrDigit(c))    sb.append(c);
        }
        return sb.toString().equals(sb.reverse().toString());
    }
0%