5. Longest Palindromic Substring**
https://leetcode.com/problems/longest-palindromic-substring/
题目描述
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"
C++ 实现 1
做这道题有个感觉是, 2 年前觉得比较难的题, 现在却能思考解出来, 这道题 LeetCode 标注为 Medium, Acceptance 只有 28.7%. 之所以可以解决, 我觉得有两点:
- 最近做题密度较大, 做了总结, 前面接触过一道关于回文串的题: 647. Palindromic Substrings**, 我做这道题的时候感觉可以参考里面的思路.
- 虽然隐约觉得可能会有更好的方法, 我不会再像 2 年前一样踌躇不定, 而是以 “解决这道题为先” 的念头着手去实现自己当前已有的想法, 先做出来再说.
事实上, 这道题一般能想到的好解法是 O(N2) 的. C++ 实现 1 的思路和 647. Palindromic Substrings** 中一样, 统计有多少个回文串, 但在这个过程中记录最长的回文串, 这一过程在 palindrome 函数中完成. 注意该函数返回 s.substr(i + 1, j - i - 1), 这个是需要斟酌的.
class Solution {
private:
string palindrome(const string &s, int i, int j) {
while (i >= 0 && j < s.size() && s[i] == s[j]) --i, ++j;
return s.substr(i + 1, j - i - 1);
}
public:
string longestPalindrome(string s) {
string res;
for (int i = 0; i < s.size(); ++ i) {
auto candidate1 = palindrome(s, i, i);
if (candidate1.size() > res.size()) res = candidate1;
auto candidate2 = palindrome(s, i, i + 1);
if (candidate2.size() > res.size()) res = candidate2;
}
return res;
}
};
C++ 实现 2
动态规划的思路, 和 和 647. Palindromic Substrings** 中一样.
class Solution {
public:
string longestPalindrome(string s) {
string res;
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) {
dp[i][j] = (s[i] == s[j]) && (j - i < 3 || dp[i + 1][j - 1]);
if (dp[i][j] && j - i + 1 > res.size()) res = s.substr(i, j - i + 1);
}
}
return res;
}
};