【LeetCode】005. 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:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

题解：

Solution 1

　　暴力搜索，所有可能，注意到"bab"和"baab"两种类型的回文字符串即可。

 class Solution {

 public:

     string longestPalindrome(string s) {

         int start = , len = ;

         int n = s.size();

         if (n < )

             return s;

         for (int i = ; i < n - ; ++i) {

             rangeOfPalindrome(s, i, i + , start, len); // "baab"

             rangeOfPalindrome(s, i, i, start, len);   // "bab"

         }

         return s.substr(start, len);

     }

     void rangeOfPalindrome(const string& s, int left, int right, int& start, int& len) {

         int length = len;

         int step = ;

         while ((left - step >= ) && (right + step < s.size())) {

             if (s[left - step] != s[right + step])

                 break;

             ++step;

         }

         length =  * (step - ) + right - left + ;

         if (length > len) {

             len = length;

             start = left - (step - );

         }

     }

 };

　　代码简化：

 class Solution {

 public:

     string longestPalindrome(string s) {

         string res;

         int n = s.size(), idx = , len = ;

         for (int i = ; i < n; ++i) {

             search(s, i, i, idx, len);

             search(s, i, i + , idx, len);

         }

         return s.substr(idx, len);

     }

     void search(const string& s, int i, int j, int& idx, int& len) {

         while (i >=  && j < s.size() && s[i] == s[j]) {

             --i;

             ++j;

         }

         if (len < j - i - ) {

             len = j - i - ;

             idx = i + ;

         }

     }

 };

Soluion 2

　　DP问题。一个长度为 n（n>1) 的回文字符串S（s1, s2,...,sn)，若将字符s0和sn+1分别放置在S的首尾，此时如果s0 == sn+1,那么新的字符串S'也一定是回文字符串。

　　那么递归式为 dp[i][j] = 1 if i == j

　　　　　　　　　　　= s[i] == s[j]　 if i + 1 = j

= s[i] == s[j] && dp[i + 1][j - 1] if i + 1 < j

 class Solution {

 public:

     string longestPalindrome(string s) {

         int n = s.size();

         if (n < )

             return s;

         int len = , start = ;

         vector<vector<int>> dp(n, vector<int>(n, ));

         for (int i = ; i < n; ++i) {

             for (int j = ; j <= i; ++j) {

                 dp[j][i] = (s[i] == s[j]) && (i - j <=  || dp[j + ][i - ]);

                 if (dp[j][i] && len < i - j + ) {

                     len = i - j + ;

                     start = j;

                 }

             }

         }

         return s.substr(start, len);

     }

 };

　　Manacher算法

Solution 3

巴特西

【LeetCode】005. Longest Palindromic Substring

最新文章

热门文章