欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode 5st Longest Palindromic Substring

程序员文章站 2024-02-01 21:33:58
...

1.题意
寻找输入字符串中的最长回文序列

2.思路比较
(1)暴力**,从头开始首尾两下标向中间移动,比较两端字符是否相同,长度控制一层循环,字符串起始位控制一层循环,比较两端字符是否相同一层循环,时间复杂度为O(n^3)代码不ac

(2)以每个字符为中心向两边扩散比较,去除长度控制这层循环,与两端标记一同控制,
时间复杂度为O(n^2)

参考代码如下:

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.size() <= 1) return s;
        int startIdx = 0, left = 0, right = 0, len = 0;
        for (int i = 0; i < s.size() - 1; ++i) {
            if (s[i] == s[i + 1]) {
                left = i;
                right = i + 1;
                searchPalindrome(s, left, right, startIdx, len);
            }
            left = right = i;
            searchPalindrome(s, left, right, startIdx, len);
        }
        return s.substr(startIdx, len);
    }
    void searchPalindrome(string s, int left, int right, int &startIdx, int &len) {
        int step = 1;
        while ((left - step) >= 0 && (right + step) < s.size()) {
            if (s[left - step] != s[right + step]) break;
            ++step;
        }
        int wide = right - left + 2 * step - 1;
        if (len < wide) {
            len = wide;
            startIdx = left - step + 1;
        }
    }
};

在处理奇偶回文序列的时候,这里使用的条件很精巧

//偶数回文序列,中间两个字符相等
if (s[i] == s[i + 1])  
//否则,直接取正中心的字符,向两侧移动
left = right = i;

另外在view code的时候,有这么一段琢磨了一会

int wide = right - left + 2 * step - 1;

式子中的-1一直很困惑,后面才发觉与初始的step=1有关,已经预先往两侧移动一步
原公式应为

int wide = right - left -1+ 2 * step + 2;

(3)动态规划算法

将已经比较好是否为回文序列的结果储存在二维数组中,减少重复比较

动态规划算法适用的情况,1最优化子结构 2无后效性 3子问题的重叠,具体学习会在另一篇博文中呈现

关键,找到状态转移方程,这里就有点像数学归纳法,两端字符相同,若子结构为真,则该结构为真

dp[i, j] = 1                                               if i == j

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

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

代码

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

动态规划的矩阵,赋值时,j-i<2涵盖了两种情况 j=i, j-1=1。

状态转移方程在代码中的体现,精妙。

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

reference:ref

相关标签: 算法 动态规划