【必备算法】字符串（回文问题）：LeetCode题 125. 验证回文串，680. 验证回文字符串 Ⅱ

浅浅的花香味﹌ 2022-12-15 12:53 144阅读 0赞

写在前面，判断是不是回文的逻辑其实很简单，就是借助双指针不断判断首尾相应位置元素是否相等，java模板如下：

boolean isPalindrom(String str, int left, int right) {
        
        while (left < right) {
        
            if (s.charAt(left) != s.charAt(right)) return false;
    	    left++; right--;
        }
        return true;
    }

--------------------

## [125. 验证回文串¹][125.] ##

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

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

**示例 1:**

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

**示例 2:**

输入: "race a car"
    输出: false

### 解法：双指针（模板） ###

本题的话，除了核心逻辑回文外，还要处理两个问题：

1.  只对字母进行判断，符号和空格跳过
2.  在进行字母相等判断时要忽略大小写

对于这两个问题，可以直接调用String提供的方法，也可以自己封装处理方法。我下面的代码没有用String提供的字符串方法。

class Solution {
        
        public boolean isPalindrome(String s) {
        
            int i = 0, j = s.length() - 1;
            while (i < j) {
        
            	// 首先判断首尾位置是否合法
                if (!isAplh(s.charAt(i))) i++;
                else if (!isAplh(s.charAt(j))) j--;
                // 合法后，判断是否回文，即相应位置元素是否相等
                else if (equalsIgnoreCase(s.charAt(i),s.charAt(j))) {
         i++; j--;} 
                else return false;
            }
            return true;
        }
    	
    	// 判断是否为字母
    	// 思路：直接用字符比大小进行，两个区间
        private boolean isAplh(char c) {
        
            return (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') || (c >= '0' && c <= '9');
        }
    	
    	// 字母相等判断，忽略大小写。
    	// 思路：若出现大写，则转化为小写，体现在代码上就是ASCII+32
        private boolean equalsIgnoreCase(char a, char b) {
        
            if (a >= 'A' && a <= 'Z') a += 32;
            if (b >= 'A' && b <= 'Z') b += 32;
            return a == b;
        }
    }

这里再把调用String的toLowerCase的解法写一下：

class Solution {
        
        public boolean isPalindrome(String s) {
        
            // 使用了String 的 toLowerCase方法。因为要将所有字母都变成小写，所以会多出来一次遍历操作。
            s = s.toLowerCase();
            int i = 0, j = s.length() - 1;
            while (i < j) {
        
                if (!isAplh(s.charAt(i))) i++;
                else if (!isAplh(s.charAt(j))) j--;
                // 此处直接比较就行，不用再写一个忽略大小写的比较函数
                else if (s.charAt(i) == s.charAt(j)) {
         i++; j--;} 
                else return false;
            }
            return true;
        }
    
        private boolean isAplh(char c) {
        
            return ((c >= 'a' && c <= 'z') || (c >= '0' && c <= '9'));
        }
    }

这个解法是的执行结果果然更长，3ms。

## [680. 验证回文字符串 Ⅱ¹][680. _] ##

给定一个非空字符串 `s`，**最多**删除一个字符。判断是否能成为回文字符串。

**示例 1:**

输入: "aba"
    输出: True

**示例 2:**

输入: "abca"
    输出: True
    解释: 你可以删除c字符。

**注意:**

1.  字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。

### 解法一：枚举法（超时） ###

*  思路：很粗暴，将所有删一个字符的情况枚举出来，然后再调用上题的逻辑判断是否回文。
 *  复杂度：
    
     *  Time：O（n²)
     *  Space：O（n）

class Solution {
        
        public boolean validPalindrome(String s) {
        
            char[] c = s.toCharArray();
            // 枚举去掉一个字符的所有结果，然后判断是否回文
            for (int i = 0; i < c.length; i++) {
        
                // 将删除位置置为‘ ’，在判断回文时会跳过
                c[i] = ' ';
                if (isPalindrome(new String(c))) return true;
                c[i] = s.charAt(i);
            }
            return false;
        }
    
        public boolean isPalindrome(String s) {
        
            int i = 0, j = s.length() - 1;
            while (i < j) {
        
                if (!(s.charAt(i) >= 'A' && s.charAt(i) <= 'Z')) i++;
                else if (!(s.charAt(j) >= 'A' && s.charAt(j) <= 'Z')) j--;
                else if (s.charAt(i) == s.charAt(j)) {
         i++; j--;} 
                else return false;
            }
            return true;
        }
    }

### 解法二：双指针（模板） ###

*  思路：若可以回文，那么前后的相应位置一定相同 —> 不断将前后不对应的位置删除，然后判断是否能成为回文串。若某次删除不能使回文，那么返回false。
 *  复杂度：
    
     *  Time：O(n)
     *  Space：O(1)

class Solution {
        
        public boolean validPalindrome(String s) {
        
            int l = 0, r = s.length() - 1;
            // 双指针，从前后开始遍历
            while (l < r) {
        
                // 找到前后不对应的位置
                if (s.charAt(l) != s.charAt(r)) 
                    // 删除 前 / 后 看是否能回文
                    // 注：所有经过循环的都是已经对应的位置，因此可以理解成删除的是一个新串的首尾，
                    //     即可以直接在当前串进行操作，通过索引模拟删除
                    return isPalindrome(s, l + 1, r) || isPalindrome(s, l, r - 1);
                l++; r--;
            }
            return true;
        }
    	// 这里只有小写字母，因此判断逻辑就是基本的双指针判断即可
        public boolean isPalindrome(String s, int l, int r) {
        
            while (l < r) {
        
                if (s.charAt(l) != s.charAt(r)) return false;
                l++; r--;
            }
            return true;
        }
    }

[125.]: https://leetcode-cn.com/problems/valid-palindrome/
[680. _]: https://leetcode-cn.com/problems/valid-palindrome-ii/