LeetCode(每日练习)-回文子串系列

港控/mmm° 2023-09-29 10:40 1阅读 0赞

> 此文章用于记录有关回文子串的的题目  
> 5. 最长回文子串  
> 剑指 Offer II 027 回文链表  
> 234. 回文链表  
> 剑指 Offer II 018 有效的回文  
> 125. 验证回文串

## 5. 最长回文子串 ##

【题目描述】  
给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = "babad"
    输出："bab"
    解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
    输出："bb"

提示：

*  1 <= s.length <= 1000
 *  s 仅由数字和英文字母组成

> 动态规划

*  回文串两边加上两个相同字符，会形成一个新的回文串  
    ![在这里插入图片描述][f12aba4c98694537b3437b2df77148f1.png]
 *  方法是，建立二维数组 dp ，找出所有的回文子串。dp\[i\]\[j\] 记录子串 i…j 是否为回文串  
    ![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3blsZXnpLo_size_20_color_FFFFFF_t_70_g_se_x_16]
 *  首先，单个字符就形成一个回文串，所以，所有 dp\[i\]\[i\] = true  
    ![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3blsZXnpLo_size_19_color_FFFFFF_t_70_g_se_x_16]
 *  如果字符 s\[i\] 和 s\[j\] 相等，并且子串 i+1…j-1 是回文串的话，子串 i…j 也是回文串。  
    也就是，如果 s\[i\] == s\[j\] 且 dp\[i+1\]\[j-1\] = true 时，dp\[i\]\[j\] = true  
    ![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3blsZXnpLo_size_20_color_FFFFFF_t_70_g_se_x_16 1]
 *  要注意边界情况，即 子串 i+1…j-1 的有效性 ，当 i+1 <= j-1 时，它才有效
 *  如果不满足，此时 j <= i+1 ，也就是子串 i…j 最多有两个字符， 如果两个字符 s\[i\] 和 s\[j\] 相等，那么是回文串
 *  可以通过一个表格，来理解整个 dp 数组的规划过程  
    ![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3blsZXnpLo_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
    上面的表格填表过程：
 *  初始化所有方格写 false 。
 *  填写对角线写 true 。
 *  自对角线右下角开始，自下而上、自左而右，按箭头方向根据递推关系填表

【AC代码】

class Solution {
        
        public String longestPalindrome(String s) {
        
            if (s.length() <= 1)
                return s;
            char[] chArr = s.toCharArray();
            int len = chArr.length;
            boolean[][] dp = new boolean[len][len];
            // 对角线初始化
            for (int i = 0; i < len; i++) dp[i][i] = true;
            int max_length = 1;
            int index_l = 0;
            for(int i = len - 1;i >=0; i--){
        
                for(int j = i ;j < len ;j++){
        
                	// 如果相等
                    if (chArr[i] == chArr[j]) {
        
                    	// 满足条件，如果前面 一个是回文串，那么这个就是回文
                        if(j - 1  >= i + 1){
        
                            dp[i][j] = dp[i + 1][j - 1];
                        }else{
        
                            dp[i][j] = true;
                        }
                    }
                    if(dp[i][j]){
        
                        int length = j - i + 1;
                        if(length > max_length){
        
                        	// 记录最大的索引和长度
                            index_l = i;
                            max_length = length;
                        }
                    }
                }
            }
            return new String(chArr,index_l ,max_length);
        }
    }

> manacher（马拉车）

【思路】

*  由于回文分为偶回文（比如 abab 长度为4）和奇回文（比如 abcba 长度为5），而在处理奇偶问题比较麻烦，所以这里需要做 个预处理，在字符间插入一个特殊字符（这个字符不能在串里出现），将原串转换统一成奇串
 *  比如原字符串： s =”abbaTNTabcba” => 插入字符之后：sNew= “$\#a\#b\#b\#a\#T\#N\#T\#a\#b\#c\#b\#a\#”
 *  算法需要一个与新串sNew等长的辅助数组int\[\] p，其中p\[i\]表示以sNew\[i\]为中心的最长回文子串的半径， 若p\[i\]=1，则该回文子串就是sNew\[i\]本身  
    ![在这里插入图片描述][382b40b0f1a042af9eeca4bdc2b3e507.png]

Manacher算法利用开头提到的回文的左边是右边的镜像，让回文串起始的对比位置尽可能的大。  
![在这里插入图片描述][41c2b5f328b2475a9a440547a41edbdc.png]  
![在这里插入图片描述][6a54f8e517c24949bb08123fed62418b.png]  
**图注：id为已知的最大回文子串中心的位置，mx是已知最大回文串的右边界，i为当前遍历到字符串的位置**  
一、mx > i  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3blsZXnpLo_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
二、mx < i　  
　　此时镜像对预判位置起不到作用，只能从长度为1开始对比，所以p\[i\] = 1。

【AC代码】

class Solution {
        
       /**
         * 最长回文子串 manacher
         * @param s
         * @return
         */
        public String manacher(String s){
        
            String str = init(s);
            int len = str.length();
            int mx = 0;
            int id = 0;
            int ans = -1;
            int[] p = new int[len];
            int index = 0;
            for(int i = 2;i < len;i++){
        
                if(i < mx){
        
                    p[i] = Math.min(mx - i,p[id * 2 - i]);
                }else{
        
                    p[i] = 1;
                }
                while (str.charAt(i + p[i] - 1) == str.charAt(i - p[i] - 1)){
        
                    p[i]++;
                }
                if(p[i] + i > mx){
        
                    mx = p[i] + i;
                    id = i;
                }
                if(ans < p[i] - 1){
        
                    ans = p[i] - 1;
                    index = i;
                }
            }
            String resStr = str.substring(index - p[index],index + p[index] - 1);
            String res = "";
            for (int i = 0; i < resStr.length(); i++) {
        
                if(resStr.charAt(i) != '@' && resStr.charAt(i) != '#'){
        
                    res += resStr.charAt(i);
                }
            }
            return res;
        }
        public  String init(String str){
        
            StringBuffer res = new StringBuffer("@#");
            for (int i = 0; i < str.length(); i++) {
        
                res.append(str.charAt(i));
                res.append("#");
            }
            res.append('%');
            return res.toString();
        }
    }

## 剑指 Offer II 027. 回文链表、234. 回文链表 ##

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：  
![在这里插入图片描述][cdb4b691ff8848648596f6aa83d26872.png]

输入：head = [1,2,2,1]
    输出：true

示例 2：  
![在这里插入图片描述][17c06606cf094fc7a94ee75e46c1a587.png]

输入：head = [1,2]
    输出：false

提示：

*  链表中节点数目在范围\[1, 105\] 内
 *  0 <= Node.val <= 9

进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？  
【解题思路】  
1、把链表的数字存入数组中，然后首尾双指针遍历判断  
2、把链表存入字符串中，反转，然后equals比较  
【AC代码】

class Solution {
        
    	// 方法一
        public boolean isPalindrome(ListNode head) {
        
            List<Integer> vals = new ArrayList<Integer>();
    
            // 将链表的值复制到数组中
            ListNode currentNode = head;
            while (currentNode != null) {
        
                vals.add(currentNode.val);
                currentNode = currentNode.next;
            }
    
            // 使用双指针判断是否回文
            int front = 0;
            int back = vals.size() - 1;
            while (front < back) {
        
                if (!vals.get(front).equals(vals.get(back))) {
        
                    return false;
                }
                front++;
                back--;
            }
            return true;
        }
        // 方法二
        public boolean isPalindrome(ListNode head) {
        
            String s1 = "";
            while (head != null){
        
                s1 += head.val;
                head = head.next;
            }
            StringBuffer buffer = new StringBuffer(s1);
            return s1.equals(buffer.reverse().toString());
        }
    }

## 剑指 Offer II 018 有效的回文、125. 验证回文串 ##

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

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

示例 1:

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

示例 2:

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

提示：

*  1 <= s.length <= 2 \* 10^5
 *  字符串 s 由 ASCII 字符组成

【思路】

*  先把有效的字符组合，然后通过双指针来判断是否回文

【AC代码】

class Solution {
        
         public boolean isPalindrome(String s) {
        
            int length = s.length();
            StringBuffer str = new StringBuffer();
            for (int i = 0; i < length; i++) {
        
                if((s.charAt(i) >= 'a' && s.charAt(i) <= 'z') || (s.charAt(i) >= 'A' && s.charAt(i) <= 'Z') || (s.charAt(i) >= '0' && s.charAt(i) <= '9')){
        
                    str.append(s.charAt(i));
                }
            }
            String s1 = str.toString();
            String s2 = s1.toUpperCase();
            int l = 0 ,r = s2.length() - 1;
            while (l <= r){
        
                if(s2.charAt(l) == s2.charAt(r)){
        
                    l++;
                    r--;
                    continue;
                }else{
        
                    return false;
                }
            }
            return true;
        }
    }

[f12aba4c98694537b3437b2df77148f1.png]: https://img-blog.csdnimg.cn/f12aba4c98694537b3437b2df77148f1.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3blsZXnpLo_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/8c3d747f27774f108b9f5a52e98f0a73.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAY3blsZXnpLo=,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3blsZXnpLo_size_19_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/664fbf29bfa94a4aa6636aeb9bd71753.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAY3blsZXnpLo=,size_19,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3blsZXnpLo_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/0ab7aeb81d374b35853778061ae2a260.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAY3blsZXnpLo=,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3blsZXnpLo_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/80508c423d8e4b34a3f3eba2575008d8.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAY3blsZXnpLo=,size_20,color_FFFFFF,t_70,g_se,x_16
[382b40b0f1a042af9eeca4bdc2b3e507.png]: https://img-blog.csdnimg.cn/382b40b0f1a042af9eeca4bdc2b3e507.png
[41c2b5f328b2475a9a440547a41edbdc.png]: https://img-blog.csdnimg.cn/41c2b5f328b2475a9a440547a41edbdc.png
[6a54f8e517c24949bb08123fed62418b.png]: https://img-blog.csdnimg.cn/6a54f8e517c24949bb08123fed62418b.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3blsZXnpLo_size_20_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/ba93850ad1ef4d12a67d53f9beb871a6.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAY3blsZXnpLo=,size_20,color_FFFFFF,t_70,g_se,x_16
[cdb4b691ff8848648596f6aa83d26872.png]: https://img-blog.csdnimg.cn/cdb4b691ff8848648596f6aa83d26872.png
[17c06606cf094fc7a94ee75e46c1a587.png]: https://img-blog.csdnimg.cn/17c06606cf094fc7a94ee75e46c1a587.png