【leetcode】有效的回文

0、相似题目

【leetcode】字符串的变位词 字符串常用方法

String相加到底创建了多少对象

StringBuffer常用API StringBuffer是线程安全的，而且append元素是直接在原字符串数组上加的。

Character常用方法 isLetterOrDigit

一、题目描述

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

本题中，将空字符串定义为有效的 回文串 。

输入: s = “A man, a plan, a canal: Panama”
输出: true
解释：“amanaplanacanalpanama” 是回文串

二、代码思路

首先、先把特殊字符过滤掉；

其次、将字母大小写处理成统一大小写。

其次，判断过滤后的字符串长度是奇数还是偶数，然后选中字符串的中间位置，依次比较对称的两边，对应位置上的字符是否相同。

2.1 代码思路2

2.1.1 思路 2.1

最简单的方法是对字符串 ss 进行一次遍历，并将其中的字母和数字字符进行保留，放在另一个字符串 sgood 中。这样我们只需要判断 sgood 是否是一个普通的回文串即可。

判断的方法有两种。第一种是使用语言中的字符串翻转 API 得到sgood 的逆序字符串 sgood_rev，只要这两个字符串相同，那么 sgood 就是回文串。

第二种是使用双指针。初始时，左右指针分别指向 sgood 的两侧，随后我们不断地将这两个指针相向移动，每次移动一步，并判断这两个指针指向的字符是否相同。当这两个指针相遇时，就说明 sgood 时回文串。

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/XltzEq/solution/you-xiao-de-hui-wen-by-leetcode-solution-uj86/
来源：力扣（LeetCode）

2.1.2 总结

• 说白了，这道题目考察的就是API的使用，以及遍历字符串的操作(双向遍历，或者双指针遍历)

   		char ch = s.charAt(i);
           if (Character.isLetterOrDigit(ch)) {
               sgood.append(Character.toLowerCase(ch));
           }
1
2
3
4

• 以及StringBuffer的相关API reverse、append、new StringBuffer(str)
• 以及转换大小写的位运算方法：

【学习基于位运算的大小写转换技巧】

从两端出发，一对一对地比较左指针和右指针字符。若不是数字或字母则跳过，若是则比较是否相等（不考虑大小写）。若调用JDK的库方法，可以借助Character.isLetterOrDigit()和Character.toLowerCase()来实现。也可以不借助库方法，编写一个isValid方法来判断是否为数字或字母，并利用位运算的技巧来实现大小写字母反转。

【基于位运算的大小写转换技巧】

观察如下四个字母的ASCII码值。
'A': 65  = 1000001
'a': 97  = 1100001
'Z': 90  = 1011010
'z': 122 = 1111010
可以发现大小写之间只差了100000，即十进制的32。
于是对于字符ch有：
ch ^ 32  大小写反转
ch | 32  大写转小写
ch & ~32 小写转大写
1
2
3
4
5
6
7
8
9
10

三、代码题解

class Solution {
    public boolean isPalindrome(String s) {
        //先把边界值处理掉，空串和含有一个空格的串
        //注意空串不能用 equals 方法
        if(s.equals(" ") || s.length() == 0) return true;
        //先对字符串进行处理，将特殊字符剔除掉：字母和数字除外
        //过滤之后的字符串
        String str = "";
        for(int i = 0; i < s.length(); i++) {
            char cr = s.charAt(i);
            if(cr >= 'a' && cr <= 'z' || 
               cr >= 'A' && cr <= 'Z' ||
               cr >= '0' && cr <= '9' ) {
                   str += cr;
               };
        }
        int length = str.length();
        //可以忽略字母的大小写,所以为了方便先把所有字符转成小写
        str = str.toLowerCase();
        if(length % 2 == 0){
            int dist = 1;
            for(int i = length / 2 - 1; i >= 0; i--) {
                //char 和 char 比较比较的是 ascii 码
                if(str.charAt(i) != str.charAt(i + dist)) return false;
                dist += 2;
            }
        }else{
            int dist = 2;
            for(int i = length / 2 - 1; i >= 0; i--) {
                //char 和 char 比较比较的是 ascii 码
                if(str.charAt(i) != str.charAt(i + dist)) return false;
                dist += 2;
            }
        }
        return true;
    }
}
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

时间复杂度：O(N)

缺点：重复性代码太多

class Solution {
    //1 <= s.length <= 2 * 105 int 长度可以搞定
    private boolean isPalindrome(int length, String str, int dist) {
        for(int i = length / 2 - 1; i >= 0; i--) {
                //char 和 char 比较比较的是 ascii 码
                if(str.charAt(i) != str.charAt(i + dist)) return false;
                dist += 2;
        }
        return true;
    }
    public boolean isPalindrome(String s) {
        //先把边界值处理掉，空串和含有一个空格的串
        //注意空串不能用 equals 方法
        if(s.equals(" ") || s.length() == 0) return true;
        //先对字符串进行处理，将特殊字符剔除掉：字母和数字除外
        //过滤之后的字符串
        String str = "";
        for(int i = 0; i < s.length(); i++) {
            char cr = s.charAt(i);
            if(cr >= 'a' && cr <= 'z' || 
               cr >= 'A' && cr <= 'Z' ||
               cr >= '0' && cr <= '9' ) {
                   str += cr;
               };
        }
        int length = str.length();
        //可以忽略字母的大小写,所以为了方便先把所有字符转成小写
        str = str.toLowerCase();
        if(length % 2 == 0){
            int dist = 1;
            return isPalindrome(length, str, dist);
        }else{
            int dist = 2;
            return isPalindrome(length, str, dist);
        }
    }
}
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