最長回文子串

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

給定一個字符串 s，找到 s 中最長的回文子串。你可以假設 s 的最大長度為 1000。

示例 1：

輸入: "babad" 輸出: "bab" 注意: "aba" 也是一個有效答案。

示例 2：

輸入: "cbbd" 輸出: "bb"

用動態規劃來做，列舉了三種解法

文章目錄

• 最長回文子串
• • 解法一
  • 解法二
  • 解法三

解法一

• 動態規劃求解：

  • map[i][j]中，i表示起點坐標，j表示長度
  • map[i][1] = 1，單個的字符同樣為回文串
  • 當s[i] == s[i+1]時候， map[i][2] = 2，連續的串同樣為回文串
  • map[i-1][j+2] = j+2 當且僅當，map[i][j]非零（即對應的字符串為回文串），且s[i-1] == s[i+j]（即，兩邊同時擴充一個位置），所以長度就是其本身

• T: 156 ms M: 14.8 MB

class Solution { public:string longestPalindrome(string s) {if (s.size() < 2)return s;int map[2000][2001];int total = 1, start=0;for (int i = 0; i < s.size(); ++i) map[i][1] = 1;for (int i = 0; i < s.size()-1; ++i){if (s[i] == s[i+1]) {map[i][2] = 2;total = 2;start = i;}else {map[i][2] = 0;}}for (int j = 3; j <= s.size(); ++j){for (int i = 0;i <= s.size() - j; ++i){if (map[i+1][j-2] != 0 && s[i] == s[i+j-1]) {map[i][j] = j;if (total < map[i][j]){total = map[i][j];start = i;}} else map[i][j] = 0;}}return s.substr(start, total);} };

解法二

• T: 124 ms M: 8.8 MB

在解法一的基礎上做了改進，目的是降低空間需求。

其實很明顯，奇數長度的回文串和偶數長度的回文串之間是沒有直接關聯的。也就是，已知回文串，兩邊同時擴張一個位置才可能有依據判斷是否為回文串。這樣的性質將回文串明顯的分為奇偶兩種可能。

• 用取余的方式判斷奇偶，就將原來的1000 * 1001的空間要求縮短到了 1000 * 2

class Solution { public:string longestPalindrome(string s) {if (s.size() < 2)return s;int map[1000][2];int total = 1, start=0;for (int i = 0; i < s.size(); ++i) map[i][1] = 1;for (int i = 0; i < s.size()-1; ++i){if (s[i] == s[i+1]) {map[i][2 % 2] = 2;total = 2;start = i;}else {map[i][2 % 2] = 0;}}for (int j = 3; j <= s.size(); ++j){for (int i = 0;i <= s.size() - j; ++i){if (map[i+1][(j-2) % 2] != 0 && s[i] == s[i+j-1]) {map[i][j%2] = j;if (total < map[i][j % 2]){total = map[i][j % 2];start = i;}} else map[i][j%2] = 0;}}return s.substr(start, total);} };

解法三

• T: 80 ms M: 9 MB

將解法二再改進為只需要一維的數組。
明顯，我們可以先做偶數長度的計算，之后，再算奇數的時候，只需要把原來的非0部分或者是更大的部分覆蓋掉就好了。

此外，這里還使用動態分配內存的方式。由于每次調用該函數時都不需要分配這么多的內存，需要的時間就會更短。
但同時對于動態分配內存，對于內存的存儲和釋放會需要更多的空間，因此空間上反而沒有更緩和。

class Solution { public:string longestPalindrome(string s) {if (s.size() < 2)return s;int *map;map = new int[s.size()+1];int total = 1, start=0;for (int i = 0; i < s.size()-1; ++i){if (s[i] == s[i+1]) {map[i] = 2;total = 2;start = i;}else {map[i] = 0;}}for (int j = 4; j <= s.size(); j+=2){for (int i = 0;i <= s.size() - j; ++i){if (map[i+1] != 0 && s[i] == s[i+j-1]) {map[i] = j;if (total < map[i]){total = map[i];start = i;}} else map[i] = 0;}}for (int i = 0; i < s.size(); ++i) if (!map[i]) map[i] = 1;for (int j = 3; j <= s.size(); j+=2){for (int i = 0;i <= s.size() - j; ++i){if (map[i+1] != 0 && s[i] == s[i+j-1]) {map[i] = j;if (total < map[i]){total = map[i];start = i;}} else map[i] = 0;}}delete[]map;return s.substr(start, total);} };

總結

以上是生活随笔為你收集整理的最长回文子串-三种DP实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。