验证回文串

题目地址：https://leetcode-cn.com/problems/valid-palindrome/

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

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

示例 1:

输入: “A man, a plan, a canal: Panama”
输出: true

示例 2:

输入: “race a car”
输出: false

解法一：双指针

首先判断两个字符串是否是回文串，就是原串与倒序是否相等，那不就是前面写的反转字符串么。只不过就是首尾交换，换成首尾是否相等。但在此之前我们先要从原串中获取数字字母串并忽略大小写

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
public boolean isPalindrome(String s) {
    if(s == null || s.length() == 0) return true;
    char[] arr = s.toCharArray();
    int n = arr.length;
    StringBuilder cs = new StringBuilder();
    for (int i = 0; i < n; i++) {
        char c = arr[i];
        if (check(c)) {
            cs.append(change(c));
        }
    }
    n = cs.length();
    for(int i = 0; i < n/2; i++){
        if(cs.charAt(i) != cs.charAt(n-i-1)){
            return false;
        }
    }
    return true;
}
//是否是字母或数字
public boolean check(char c){
    return c>=48&&c<=57 || c>=65&&c<=90 || c>=97&&c<=122;
}
//大写统一转小写
public char change(char c){
    return c>=65&&c<=90 ? c+=32 : c;
}

解法二：细节优化(双指针)

我们刚刚是用了两个循环，第一个循环筛选了属于字母数字的。第二次循环再判断字母数字的串有木有重复。其实是冗余的，我们直接在第一个循环完成即可，最终的目的是看字母数字是否回文但没必要取出来再做。那样减少了一个容器和一次遍历。

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
public boolean isPalindrome(String s) {
    if(s == null || s.length() == 0) return true;
    char[] arr = s.toCharArray();
    int n = arr.length;
    
    int start = 0;
    int end = n - 1;
    while(start < end){
        while(start < end && !check(arr[start])){
            start++;
        }
        while(start < end && !check(arr[end])){
            end--;
        }
        if(change(arr[start])!=change(arr[end])){
            return false;
        }
        start++;
        end--;
    }
    return true;
}
//是否是字母或数字
public boolean check(char c){
    return c>=48&&c<=57 || c>=65&&c<=90 || c>=97&&c<=122;
}
//大写统一转小写
public char change(char c){
    return c>=65&&c<=90 ? c+=32 : c;
}

解法三：栈

虽然这题双指针就是比较优的解法，但是前段时间学习了栈，因此在这题上用上温习一下不过空间和效率应该是最低的，我们都知道栈是后进先出（LIFO）一种数据结构。这里我们可以用数组实现一下栈完成一下基本的四个方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Stack<E>{
    List<E> arr = new ArrayList();
    int top = -1;        
    void push(E c){
        arr.add(++top,c);
    }
    E pop(){
        E c = peek();
        arr.remove(top--);
        return c;
    }
    E peek(){
        return arr.get(top);
    }
    boolean isEmpty(){
        return top < 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public boolean isPalindrome(String s) {
    if(s == null || s.length() == 0) return true;
    char[] arr = s.toCharArray();
    int n = arr.length;
    Stack<Character> stack = new Stack<>();
    List<Character> list = new ArrayList<>();
        
    for (int i = 0; i < n; i++) {
        char c = arr[i];
        if (check(c)){
            stack.push(change(c));
            list.add(change(c));
        }
    }
    int index = 0;
    while (!stack.isEmpty()){
        if (stack.pop() != list.get(index++))
            return false;
    }
    return true;
}

总结

回文串处理的大体方式还是双指针、反转或者栈。对于此题Character类中提供了判断是否为数字或字母的方法和转大小写的方法。我上面是单独写的check(char c)与change(char c)方法。

1
2
isLetterOrDigit(char c)
toLowerCase(char c)

利用Java类库的话直接有反转方法当然它里面也是一次遍历处理，反转再比较。当然效率是比较低的可以参考

1
2
3
//cs为取出来的只含字母数字的字符串
String fz = cs.reverse().toString();
return cs.equals(fz);

总体来说呢可以实现的方式有很多，关注实现本身效率来说双指针是较优的。