(动态规划) 5. 最长回文子串 ——【Leetcode每日一题】

❓ 5. 最长回文子串

难度：中等

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

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

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

示例 2：

输入：s = “cbbd”
输出：“bb”

提示：

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

💡思路：

法一：中心点扩展法

首先确定回文串，就是找中心然后想两边扩散看是不是对称的就可以了。

一个元素可以作为中心点；
两个元素也可以作为中心点。

法二：动态规划

定义 dp 数组，dp[i][j] 表示区间范围 [i,j] （注意是左闭右闭）的子串是否是回文子串，如果是 dp[i][j] 为 true，否则为 false 。

要从下到上，从左到右遍历，当 s[i] 与 s[j] 相等时，有如下三种情况:

下标 i 与 j 相同，同一个字符例如 a，当然是回文子串
下标 i 与 j 相差为1，例如 aa，也是文子串
下标：i 与 j 相差大于1的时候，例如 cabac，此时 s[i] 与 s[j] 已经相同了，我们看 i 到 j 区间是不是回文子串就看 aba 是不是回文就可以了，那么 aba 的区间就是 i+1 与 j-1区间，这个区间是不是回文就看 dp[i + 1][j - 1] 是否为 true。

🍁代码：(C++、Java)

法一：中心点扩展法
C++

class Solution {
private:int strLen (string s, int l, int r){while(l >= 0 && r < s.size()){if(s[l] == s[r]){l--; r++;}else break;}return r - l - 1;}
public:string longestPalindrome(string s) {int mid = 0, len = 0;int n = s.size();for(int i = 0; i < n; i++){int tmp = strLen(s, i - 1, i + 1);if(i < n - 1 && s[i] == s[i + 1]) {tmp = max(tmp, strLen(s, i - 1, i + 2));} if(tmp > len){mid = i;len = tmp;}}//记录开始点int start = mid - len / 2;if(len % 2 == 0) start += 1;return s.substr(start, len);}
};

Java

class Solution {private int strLen (String s, int l, int r){while(l >= 0 && r < s.length()){if(s.charAt(l) == s.charAt(r)){l--; r++;}else break;}return r - l - 1;}public String longestPalindrome(String s) {int mid = 0, len = 0;int n = s.length();for(int i = 0; i < n; i++){int tmp = strLen(s, i - 1, i + 1);if(i < n - 1 && s.charAt(i) == s.charAt(i + 1)) {tmp = Math.max(tmp, strLen(s, i - 1, i + 2));} if(tmp > len){mid = i;len = tmp;}}//记录开始点int start = mid -len / 2;if(len % 2 == 0) start += 1;return s.substring(start, start + len);}
}

法二：动态规划
C++

class Solution {
public:string longestPalindrome(string s) {vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));int start = 0;int len = 0;for(int i = s.size() - 1; i >= 0; i--){for(int j = i; j < s.size(); j++){if(s[i] == s[j]){if(j - i <= 1 ||dp[i + 1][j - 1]) dp[i][j] = 1;}if(dp[i][j] && j - i + 1 > len){len = j - i + 1;start = i;}}}return s.substr(start, len);}
};

Java

class Solution {public String longestPalindrome(String s) {boolean[][] dp = new boolean[s.length()][s.length()];int start = 0;int len = 0;for(int i = s.length() - 1; i >= 0; i--){for(int j = i; j < s.length(); j++){if(s.charAt(i) == s.charAt(j)){if(j - i <= 1 ||dp[i + 1][j - 1]) dp[i][j] = true;}if(dp[i][j] && j - i + 1 > len){len = j - i + 1;start = i;}}}return s.substring(start, start + len);}
}