【算法刷题】-最长回文子串-白红宇

【算法刷题】-最长回文子串

阅读量：3929 次

发布时间：2019-05-23

本文共 3596 字，大约阅读时间需要 11 分钟。

微信搜索：编程笔记本。获取更多干货！

点击上方蓝字关注我，我们一起学编程

欢迎小伙伴们分享、转载、私信、赞赏

最长回文子串

文章目录

所谓回文串，就是正序和逆序都相同的子串（上海自来水来自海上）。子串是原字符串的连续部分，这区别于子序列。

微信搜索：编程笔记本。获取更多干货！

1. 暴力枚举法

时间复杂度：O(n^3)

空间复杂度：O(1)

class Solution {
   public:    string longestPalindrome(string s)    {
           int len = s.size();            if (len <= 1) {
               return s;        }            int maxLen = 1;    /* 回文串的最大长度 */        int begin = 0;     /* 回文串的起始下标 */            for (int i = 0; i < len - 1; ++i) {
               /* 从大于最大长度的位置开始遍历 */            for (int j = i + maxLen ; j < len; ++j) {
                   if (isPalindrome(s, i, j)) {
                       maxLen = j - i + 1;                    begin = i;                }            }        }                return s.substr(begin, maxLen);    }        /* 判断是否为回文串 */    bool isPalindrome(const string& s, int start, int end)    {
           bool ispalindrome = true;                while (start < end) {
               if (s[start++] != s[end--]) {
                   ispalindrome = false;                break;            }        }                return ispalindrome;    }};

2. 中心扩展法

分析：

微信搜索：编程笔记本。获取更多干货！

枚举所有可能的回文子串的中心位置，中心位置可能是一个字符（奇数长度），也可能是两个相邻的字符（偶数长度）。

时间复杂度：O(n^2)

空间复杂度：O(1)

class Solution {
   public:    string longestPalindrome(string s)    {
           int len = s.size();            if (len <= 1) {
               return s;        }            int maxLen = 1;    /* 回文串的最大长度 */        int begin = 0;     /* 回文串的起始下标 */            for (int i = 0; i < len - 1; ++i) {
               int oddLen = expandAroundCenter(s, i, i);         /* 回文串的中心为单个字符 */            int evenLen = expandAroundCenter(s, i, i + 1);    /* 回文串的中心为两个相邻的字符 */            int curMaxLen = max(oddLen, evenLen);                        if (curMaxLen > maxLen) {
                   maxLen = curMaxLen;                begin = i - (maxLen - 1) / 2;    /* 计算当前最大回文串的起始下标 */            }        }                return s.substr(begin, maxLen);    }        /* 从中心往两边扩展，寻找最长回文子串的长度 */    int expandAroundCenter(const string& s, int left, int right)    {
           int len = s.size();        int i = left;        int j = right;                while (i >= 0 && j < len) {
               if (s[i] == s[j]) {
                   --i;                ++j;            } else {
                   break;            }        }                return j - i - 1;    }};

3. 动态规划法

分析：

状态： dp[i][j] 表示子串 s[i...j] 是否为回文子串；

状态转移方程：dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1] ；

初始化：dp[i][i] = true ；

输出：在得到一个状态的值为 true 的时候，记录起始位置和长度，填表完成以后再截取。

微信搜索：编程笔记本。获取更多干货！

时间复杂度：O(n^2)

空间复杂度：O(n^2)

class Solution {
   public:    string longestPalindrome(string s)    {
           int len = s.size();            if (len <= 1) {
               return s;        }            int maxLen = 1;    /* 回文串的最大长度 */        int begin = 0;     /* 回文串的起始下标 */                vector
   
    
     > dp(len, vector
     
      (len, true));            for (int j = 1; j < len; ++j) {
               for (int i = 0; i < j; ++i) {
                   if (s[i] != s[j]) {
                       dp[i][j] = false;                } else {
                       dp[i][j] = (j - i <= 2) ? true : dp[i + 1][j - 1];                }                                if (dp[i][j] && j - i + 1 > maxLen) {
                       maxLen = j - i + 1;                    begin = i;                }            }        }                return s.substr(begin, maxLen);    }};

4. Manacher 算法

时间复杂度为 O(n) 。该算法十分复杂，有兴趣的童鞋可以自己查阅相关资料。

微信搜索：编程笔记本。获取更多干货！

你可能感兴趣的文章