【LeetCode】回文串专题

目录

【LeetCode】5.最长回文子串

【LeetCode】680. 验证回文字符串 Ⅱ

---

【LeetCode】5.最长回文子串

题目链接

https://leetcode-cn.com/problems/longest-palindromic-substring/

题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：
输入: "cbbd"
输出: "bb"

解题思路

(1)暴力求解

字符串问题，首先就是想到暴力的方法。

找出字符串s的所有子串，并对所有子串进行判断其是否为回文串，如果字符串s有多个不同长度的回文子串，则用ans以及maxx迭代更新最长回文子串以及最长回文子串的长度。时间复杂度为O(n³)，基本上是超时的。

(2)中心扩展法

思路：

• 长度为奇数的回文子串中心有一个元素，例如 "aba" 的中心元素为 "b" ；

• 长度为偶数的回文子串中心有两个元素，例如 "abba" 的中心元素为 "bb" 。

• 分别以两种中心为基础寻找并比较出最长回文子串。

(3)动态规划(本题的解法与LCS类型)

动态规划一般也只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解(对有些问题这个要求并不能完全满足，故有时需要引入一定的近似)。简单地说，问题能够分解成子问题来解决。

动态规划算法分以下4个步骤：

（1）描述最优解的结构
（2）递归定义最优解的值
（3）按自底向上的方式计算最优解的值   //此3步构成动态规划解的基础。
（4）由计算出的结果构造一个最优解。   //此步如果只要求计算最优解的值时，可省略。
好，接下来，咱们讨论适合采用动态规划方法的最优化问题的俩个要素：最优子结构性质，和子问题重叠性质。

（1）最优子结构
    如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。意思就是，总问题包含很多个子问题，而这些子问题的解也是最优的。

（2）重叠子问题
    子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。

该问题满足最优子结构性质：一个最长回文串去掉两头以后，剩下的部分依然是最长回文串。

第一步：定义状态

dp[i][j]：表示子串s[i,j]是否为回文子串。

当dp[i][j] = 1：表示子串s[i,j]为回文子串，反之。

第二步：状态转移方程

这一步在做分类讨论（根据头尾字符是否相等）。

 if j-i >= 2

dp[i][j] = 1, if dp[i+1][j-1] == 1 && s[i] == s[j]

dp[i][j] = 0, if dp[i+1][j-1] == 0 || s[i] != s[j]

else

dp[i][j] = 1，if s[i] == s[j]

dp[i][j] = 0，if s[i] != s[j]

Q：j-i >= 2这个条件是如何求解出来的？

A：因为dp[i][j]表示子串s[i,j]是否为回文子串，所以i<=j,同理dp[i+1][j-1]中,i+1 <= j-1，整理得j - i <= 2.

第三步：考虑初始化

初始化的时候，单个字符一定是回文串，因此把对角线先初始化为 1，即 dp[i][i] = 1 。

第四步：考虑输出

只要一得到dp[i][j] = 1，就记录子串的长度和起始位置，没必要利用substr函数截取，因为截取字符串也要消耗性能，记录此时的回文子串的“起始位置”和“回文长度”即可。

第五步：考虑状态是否可以压缩
因为在填表的过程中，只参考了左下方的数值。事实上可以压缩，但会增加一些判断语句，增加代码编写和理解的难度，丢失可读性。在这里不做状态压缩。

(4)观察法

观察子串，回文字数要么是偶数个，那么类似cbaabc这种中间是aa的；要么是奇数个，类似是cbabc中间是bab型的，仅此两种。所以用for先找偶数型（aa)回文，找s[i]=s[i+1]，找到后再往两边推，直到s[i-len]与s[i+1+len]不等为止，记录此子串的位置和长度，最后进行长度比较。再找s[i]=s[i+2]，即找奇数型（aba）回文，找到后处理同上。

AC代码

(2) 中心扩展法

class Solution {
    public String longestPalindrome(String s) {
        if (s.isEmpty()) {
            return "";
        }
        // 记录最长回文子串开始和结束的位置。
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            // 查找以当前元素为中心的最长回文子串长度。
            int len1 = function(s, i, i);
            // 查找以当前元素和下一个元素为中心的最长回文子串长度。
            int len2 = function(s, i, i + 1);
            int maxLen = Math.max(len1, len2);
            // 判断记录遍历过位置能找到的最长回文子串起始位置。
            if (maxLen > end - start) {
                start = i - (maxLen - 1) / 2;
                end = i + maxLen / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private int function(String s, int left, int right) {
        // 以传入的相邻两位置为中心找最大回文子串长度，两位置相同表示一个元素为中心。
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

(3)动态规划法

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.size() == 0 || s.size() == 1 || (s.size() == 2 && s[0] == s[1])) return s;
        vector<vector<int> > dp(s.size(),vector<int>(s.size())); //二维vector数组的初始化方式
        int index = 0;
        int len = 0;
        for(int i = 0; i < s.size(); i++) dp[i][i]=1;
        for(int j = 1; j < s.size(); j++)
        {
            for(int i = 0; i < j; i++)
            {
                if(j - i < 2)
                {
                    if(s[i] == s[j]) dp[i][j] = 1; //dp[i][j]=1表示字符串s[i]-s[j]为回文串，反之。
                    else dp[i][j] = 0;
                }
                else
                {
                    if(dp[i+1][j-1] == 1 && s[i] == s[j]) dp[i][j] = 1;
                    else dp[i][j] = 0;
                }
                
                if(dp[i][j] == 1 && j-i+1>len) //迭代更新，利用len记录回文串的最大长度
                {
                    index = i;
                    len = j-i+1;
                }
            }
        }
        if(len == 0) return s.substr(0,1);
        else return s.substr(index,len);
    }
};

(4)观察法

class Solution {
public:
string longestPalindrome(string s) 
{
    const int slen = s.length();
    int i,t;
    int max = 0;
    t = 0;
    for (i = 0; i < slen; i++) //该for循环判断cbaabc类型的回文串
    {
        if(s[i]==s[i+1])
            {
                int hlen=1;
                while((i-hlen>=0) && (i+1+hlen<=slen-1)&&(s[i-hlen]==s[i+1+hlen]))
                    hlen++;
                if (2 * hlen > max)
                {
                    max = 2 * hlen;
                    t = i-hlen+1;
                }
            }
    }
    for (i = 0; i < slen-1; i++)//该for循环判断cbabc类型的回文串
    {
        if (s[i] == s[i + 2])
        {
            int hlen = 1;
            while ((i - hlen >= 0 //防止数组下标越界) && (i + 2 + hlen <= slen-1//防止数组下标越界) && (s[i - hlen] == s[i + 2 + hlen]))
                hlen++;
            if (2 * hlen + 1 > max)
            {
                max = 2 * hlen + 1;
                t = i-hlen+1;
            }
        }
    }
    if (max==0)
        return s.substr(0,1);
    else
        return s.substr(t, max);
}
};

【LeetCode】680. 验证回文字符串 Ⅱ

题目链接

https://leetcode-cn.com/problems/valid-palindrome-ii/

题目描述

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

示例 1:
输入: "aba"
输出: True

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

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

解题思路

1.暴力枚举

先判断字符串S是否为回文字符串，如果是则返回true，如果不是按顺序删除字符串S中的每一个字符，然后判断剩余的字符串是否为回文字符串即可。

2.双指针

当检查到前后不一样的字符，必须要删掉一个（要么开头，要么结尾）。删掉之后检查剩下的字符串是否为回文。是则返回TRUE，反之。

AC代码

双指针

class Solution {
public:
    bool ispalindrome(string s) //判读字符串S是否为回文字符串，这样的时间复杂度为O(n/2)
    {
        int start = 0;
        int end = s.size()-1;
        while(start <= end)
        {
            if(s[start] != s[end]) return false;
            start++;
            end--;
        }
        return true;
    }
    bool validPalindrome(string s) {
        int start = 0;
        int end = s.size()-1;
        if(s.size()<=2) return true;
        while(start <= end)
        {
            if(s[start] == s[end])
            {
                start++;
                end--;
            }
            else
            {
                int len = end-start;
                string temp = s.substr(start+1,len);//当两个元素不相同时，删除前面一个元素，判断剩下的元素是否为回文串
                if(ispalindrome(temp)) return true;
                string te = s.substr(start,len);//当两个元素不相同时，删除后面一个元素，判断剩下的元素是否为回文串
                if(ispalindrome(te)) return true;
                return false;
            }
        }
        return true;
    }
};