[LeetCode — 5] 最长回文串

目录

1.题目描述

2.解决方案

1.题目描述

    题目链接：最长回文串

    给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 

示例 1：

输入: "babad"

输出: "bab"

注意: "aba" 也是一个有效答案。

示例 2

输入: "cbbd"

输出: "bb"

2.解决方案

    方法一： 动态规划

    算法

    用二位数组来标记字符串从下标 i 到下标 j 是否为回文串。

    对于当前要判断的区间 [i, j]：

• 如果 i == j：dp[i][j] = true；
• 如果 i +1 == j：当 s[i] == s[j] 时 dp[i][j] = true；否则 dp[i][j] = false；
• 对于一般情形：如果 s[i] != s[j]，则 dp[i][j] = false；如果 s[i] == s[j]，当 dp[i+1][j-1] = true 时 dp[i][j] = true；否则 dp[i][j] = false；

    上述分析一般情形时发现，对区间 [i, j] 的判断要依赖区间 [i+1,j-1]，所以 i 应该从大变小，j 应该从小变大。并且每轮循环中 j 的初始值设为 i 就可以。

    对于字符串 "CBBA" 而言，具体情况如下图：

    代码链接：看代码，点这里嗷~

    复杂度分析

时间复杂度：O(N^2)，两层 for 循环。

空间复杂度：O(N^2)，使用二维数组来标记字符串从下标 i 到下表 j 是否为回文串。 

最后

以上就是隐形马里奥为你收集整理的[LeetCode — 5] 最长回文串的全部内容，希望文章能够帮你解决[LeetCode — 5] 最长回文串所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。