DP之回文串合集

9. 回文数

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

• 例如，121 是回文，而 123 不是。

示例 1：

输入：x = 121
输出：true

示例 2：

输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3：

输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。

提示：

• -231 <= x <= 231 - 1

C++

class Solution {
public:
    bool isPalindrome(int x) {
        string s = to_string(x);
        string s1 = s;
        reverse(s.begin(), s.end());
        return s == s1;
    }
};

409. 最长回文串

给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的回文串 。

在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。

示例 1:

输入:s = "abccccdd"
输出:7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

示例 2:

输入:s = "a"
输入:1

提示:

• 1 <= s.length <= 2000
• s 只由小写 和/或 大写英文字母组成

C++

class Solution {
public:
    int longestPalindrome(string s) {
        int res = 0;
        map<char, int> mp;
        for(char ch : s){
            mp[ch]++;
        }
        for(auto i : mp){
            int o = i.second;
            res += o/2 * 2; // res 一加都加的是偶数
            if(res % 2 == 0 && o % 2 == 1){ // 当有出现次数为单数的, res变为奇数下次再遇见出现次数为单数的,res不增加
                res += 1;
            }
        }
        return res;
    }
};

125. 验证回文串

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

示例 1：

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

示例 2：

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

示例 3：

输入：s = " "
输出：true
解释：在移除非字母数字字符之后，s 是一个空字符串 "" 。
由于空字符串正着反着读都一样，所以是回文串。

提示：

• 1 <= s.length <= 2 * 105
• s 仅由可打印的 ASCII 字符组成

C++

class Solution {
public:
    bool isPalindrome(string s) {
        string sgood;
        for (char ch: s) {
            if (isalnum(ch)) { // 判断字符变量c是否为字母或数字，若是则返回非零，否则返回零。
                sgood += tolower(ch);
            }
        }
        string sgood_rev(sgood.rbegin(), sgood.rend());
        return sgood == sgood_rev;
    }
};

680. 验证回文串 II

给你一个字符串 s，最多 可以从中删除一个字符。

请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。

示例 1：

输入：s = "aba"
输出：true

示例 2：

输入：s = "abca"
输出：true
解释：你可以删除字符 'c' 。

示例 3：

输入：s = "abc"
输出：false

提示：

• 1 <= s.length <= 105
• s 由小写英文字母组成

C++

// 正确版本
class Solution {
public:
    bool validPalindrome(string s) {
        int l = 0;
        int r = s.size() - 1;
        while(l <= r ){
            if(s[l] != s[r]){
                return isValid(s, l + 1, r) || isValid(s, l, r - 1);
            } 
            l ++;
            r --;
        }
        return true;
    }

    bool isValid(string s, int l, int r){
        while(l <= r){
            if(s[l] != s[r]) return false;
            l ++;
            r --;
        }
        return true;
    }
};

// 错误版本
class Solution {
public:
    int res = 0;
    bool validPalindrome(string s) {
        int l = 0;
        int r = s.size() - 1;
        while(l <= r && res <= 1){
            if(s[l] != s[r]){
                if(s[l + 1] == s[r]) { //错在不能第一种情况符合就不执行第二种
                    l ++;
                    res ++;
                }
                else if(s[l] == s[r - 1]){
                    r --;
                    res ++;
                }
                else return false;
            } 
            l ++;
            r --;
        }
        return res <= 1 ? true : false;
    }
};

5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

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

示例 2：

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

提示：

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

C++

class Solution {
public:
    int max = 0;
    int begin = 0;
    int end = 0;
    string longestPalindrome(string s) {
        int n = s.size();
        if(n <= 1) return s;
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        for(int i = n - 1; i >= 0; i --){
            for(int j = i; j < n; j ++){
                if(j - i < 1) dp[i][j] = true;
                else if(j - i == 1) dp[i][j] = s[i] == s[j];
                else dp[i][j] = s[i] == s[j] && dp[i + 1][j - 1]; // 如果没有else 那么当i = n - 1时, i + 1 越界
                if (dp[i][j] && j - i + 1 > max) {
                    max = j - i + 1;
                    begin = i;
                    end = j;
                }
            }
        }
        return s.substr(begin, max);
    }
};

647. 回文子串

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：

输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：

• 1 <= s.length <= 1000
• s 由小写英文字母组成

C++

class Solution {
public:
    int res = 0;
    int countSubstrings(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        for(int i = n - 1; i >= 0; i --){
            for(int j = i; j < n; j ++){
                if(j - i < 1) dp[i][j] = true;
                else if(j - i == 1) dp[i][j] = s[i] == s[j];
                else dp[i][j] = s[i] == s[j] && dp[i + 1][j - 1];
                if(dp[i][j] == true) res ++;
            }
        }
        return res;
    }
};

131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a"
输出：[["a"]]

提示：

• 1 <= s.length <= 16
• s 仅由小写英文字母组成

C++

class Solution {
public:
    vector<vector<string>> res;

    vector<vector<string>> partition(string s) {
        dfs(s, {});
        return res;
    }

    void dfs(string s, vector<string> path) {
        if (s.size() == 0) {
            res.push_back(path);
            // path.clear();
            return;
        }
        for (int i = 1; i <= s.size(); i++) {
            string pre = s.substr(0, i);
            if (isPalindrome(pre)) {
                path.push_back(pre);
                dfs(s.substr(i), path);
                path.pop_back();
            }
        }
    }

    bool isPalindrome(string s) {
        if (s.size() == 0) return true;
        int l = 0, r = s.size() - 1;
        while (l <= r) {
            if (s[l] != s[r])
                return false;
            l ++;
            r --;
        }
        return true;
    }

};

132. 分割回文串 II

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。

返回符合要求的 最少分割次数 。

示例 1：

输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

示例 2：

输入：s = "a"
输出：0

示例 3：

输入：s = "ab"
输出：1

提示：

• 1 <= s.length <= 2000
• s 仅由小写英文字母组成

C++

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        if(n == 1) return 0;
        if(n == 2) return s[0] == s[1] ? 0 : 1;
        vector<int> dp(n, INT_MAX);
        vector<vector<bool>> res = isPalindrome(s);
        dp[0] = 0;
        dp[1] = s[0] == s[1] ? 0 : 1;
        for(int r = 2; r < n; r ++){
            for(int l = 0; l <= r; l ++){
                if(res[l][r]){
                    if(l > 0) dp[r] = min(dp[r], dp[l - 1] + 1);
                    else dp[r] = 0;
                }
            }
        }
        return dp[n - 1];
    }

  	//用双指针判断会超时
    vector<vector<bool>> isPalindrome(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        for(int i = n - 1; i >= 0; i --){
            for(int j = i; j < n; j ++){
                if(j - i < 1) dp[i][j] = true;
                else if(j - i == 1) dp[i][j] = s[i] == s[j];
                else dp[i][j] = s[i] == s[j] && dp[i + 1][j - 1];
            }
        }
        return dp;
    }
};

516. 最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：

输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

示例 2：

输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。

提示：

• 1 <= s.length <= 1000
• s 仅由小写英文字母组成

C++

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for(int i = n - 1; i >= 0; i --){
            for(int j = i; j < n; j ++){
                if(j - i < 1) dp[i][j] = 1;
                else if(j - i == 1) dp[i][j] = s[i] == s[j] ? 2 : 1;
                else if(s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2;
                else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
        return dp[0][n - 1];
    }
};