[LeetCode系列] 最长回文子串问题

给定字符串S, 找到其子串中最长的回文字符串.

反转法: 反转S为S', 找到其中的最长公共子串s, 并确认子串s在S中的下标iS与在S'中的下标iS'是否满足式: length(S) = iS + iS' + length(s). 如果满足则s为搜索结果, 如果不满足我们就继续搜索.

DP解法:

定义 P[i][j] = true <-> Si...Sj是回文串, 否则为false;

则有 P[i+1][j-1] = true && Si = Sj <-> P[i][j] = true;

基本的情况则是 P[i][i] = true 以及 P[i][i+1] = (Si == Si+1)

从而我们可以在平方时间内构造和搜索完成, 并使用平方的空间.

 class Solution {

 public:

     string longestPalindrome(string s) {

         if (s.length() <= ) return s;

         // DP solution

         bool P[][] = {false};

         int start = ;

         int maxLen = ;

         for (int i = ; i < s.length(); i++) {

             P[i][i] = true;

         }

         for (int i = ; i < s.length() - ; i++) {

             if (s[i] == s[i+]) {

                 P[i][i+] = true;

                 start = i;

                 maxLen = ;

             }

         }

         for (int len = ; len <= s.length(); len++) {

             for (int i = ; i < s.length() - len + ; i++) {

                 int j = i + len - ;

                 if (s[j] == s[i] && P[i+][j-]) {

                     P[i][j] = true;

                     start = i;

                     maxLen = len;

                 }

             }

         }

         return s.substr(start, maxLen);

     }

 };

中心法:

一个回文总是以某个字符为中心展开的, 这样的中心共有2N-1个(包括2个字符中间的"空白").

考虑到从中心开始拓展回文字符需要消耗O(N)次, 所以总的时间复杂度是O(N2).

 class Solution {

 public:

     string longestPalindrome(string s) {

         if (s.length() <= ) return s;

         string longest = s.substr(, );

         // Center Solution

         for (int i = ; i < s.length() - ; i++) {

             string res = expandFromCenter(s, i, i);

             if (res.length() > longest.length()) longest = res;

             res = expandFromCenter(s, i, i+);

             if (res.length() > longest.length()) longest = res;

         }

         return longest;

     }

     string expandFromCenter(string s, int l, int r) {

         while (l >=  && r < s.length() && s[l] == s[r]) {

             l--;

             r++;

         }

         return s.substr(l+, r-l-);

     }

 };

Manacher法: 线性时间解法, 比较复杂, 戳.

巴特西

[LeetCode系列] 最长回文子串问题

最新文章

热门文章