~ read.

leetcode5 最长回文子串

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

 

示例 1:

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

输入:s = "cbbd"
输出:"bb"
示例 3:

输入:s = "a"
输出:"a"
示例 4:

输入:s = "ac"
输出:"a"

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解:
采用动态规划算法,形成一个二维表格,满足条件的置位true,最后找最长的

#include <iostream>
#include <vector>
using namespace std;

void Print(vector<vector<bool> >& v) {
    for (int i = 0; i < v.size(); ++i) {
        for (int j = 0; j < v[i].size(); ++j) {
            cout << v[i][j];
        }
        cout << endl;
    }
    return;
}
// dp[i][j] 表 i~j 为回文子串
// dp[i+1][j-1] 也应为回文子串
// 横轴i,纵轴j
class Solution {
public:
    string longestPalindrome(string s) {
        if (2 > s.length()) { return s; }

        int begin = 0;
        int len   = 1;
        vector<vector<bool> > dp(s.length(), vector<bool>(s.length()));
        for (int i = 0; i < s.length(); ++i) {
            dp[i][i] = true;  // i==j 时,即单个元素构成回文
        }
        for (int j = 1; j < s.length(); ++j) {
            for (int i = 0; i < j; ++i) {
                if (s.at(i) != s.at(j)) {
                    dp[i][j] = false;
                } else {
                    // if ((j-1) - (i+1) + 1 < 2) {  // i == j, i+1 ~ j-1 区间小于2,意味着 ij 回文
                    if (j - i < 3) {  // i == j, i+1 ~ j-1 区间小于2,意味着 ij 回文
                        dp[i][j] = true;
                    } else {    // i == j, 区间大于2, 继续缩小区间进行判断
                        dp[i][j] = dp[i+1][j-1];
                    }
                }

                // dp[i][j] == true, 表示ij 是回文, 记录最长的
                if (dp[i][j] && j-i+1 > len) {
                    begin = i;
                    len = j-i+1;
                }
            }
        }

        // Print(dp);

        return s.substr(begin, len);
    }
};


int main() {
    Solution s;
    cout << s.longestPalindrome("babad") << endl;
    cout << s.longestPalindrome("cbbd") << endl;
    cout << s.longestPalindrome("a") << endl;
    cout << s.longestPalindrome("ac") << endl;

    return 0;
}