摘要：题目描述给定一个字符串，找到中最长的回文子串。你可以假设的最大长度为。示例输入输出注意也是一个有效答案。示例输入输出思路分析暴力解法解决一个问题如果没有思路，就要想办法从简单粗暴的解法开始，然后想办法优化它。
题目描述
https://leetcode-cn.com/probl...
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"思路分析 暴力解法
输出: "bb"
解决一个问题如果没有思路，就要想办法从简单粗暴的解法开始，然后想办法优化它。
以"babad"为例，
子串长度为1的时候，必然是回文
子串长度为2的时候，[ba,ab,ba,ad]，需要两个字符串相等才是回文
子串长度为3的时候，[bab,aba,bad]，需要从两边向中心依次判断字符是否相等
子串长度为4的时候，[baba,abad]。判断方式同3
...
因此得到了一个暴力的解法，就是三层循环，
第一层循环是子串的长度规模(12345)
第二层循环是遍历每个子串(ba ab ba ad)
第三层循环是对比首尾的字符是否相等
时间复杂度
$$ O(n^3) $$
空间复杂度
$$ O(1) $$
动态规划子串长度为1的时候，必然是回文
子串长度为2的时候，[ba,ab,ba,ad]，需要两个字符串相等才是回文
子串长度为3的时候，[bab,aba,bad]，需要从两边向中心依次判断字符是否相等
子串长度为4的时候，[baba,abad]。判断方式同3
...
基于暴力解法，我们发现3是可以复用1的结论的，4是可以复用2的结论的，5是可以复用3的结论的，因此就发现了DP的一个要素（重叠子问题）
DP的其它要素是最优子结构、子问题独立，以及状态转移方程
状态转移方程：
dpi表示子串长度为i时，从j开头的子串是否为回文
s表示字符串
$$ dp[i][j] = egin{equation} egin{cases} true,&i=1 s[j] == s[j+1],&i=2 dp[i-2][j] && s[j]==s[j+i],&其它 end{cases} end{equation} $$
长度为1的时候必然是回文，
长度为2的时候取决于前后两个字符串是否相等
其它情况则3看1,4看2，这样看之前的是否是回文，然后判断子串的首尾两个是否是回文
根据状态转移方程填写dp数组，最后得到问题结果
时间复杂度
$$ O(n^2) $$
空间复杂度
$$ O(n^2) $$
中心扩展法然后再基于动态规划解法的思路，分析下能否进一步缩小空间复杂度
todo
public class MyDpSolution {
public String longestPalindrome(String s) {
if(s == null || s.length() == 0) {
return "";
}
boolean[][] dp = new boolean[s.length()][s.length()];
for(int i = 0; i < s.length(); i++) {
// i表示规格
for(int j = 0; j < s.length() - i; j++){
if(i == 0){
dp[i][j] = true;
} else if(i == 1) {
dp[i][j]= s.charAt(j) == s.charAt(j+1);
} else {
dp[i][j] = s.charAt(j) == s.charAt(j+i) && dp[i-2][j+1];
}
}
}
for(int i = s.length() - 1; i >= 0; i--) {
for(int j = 0; j + i < s.length(); j++) {
if(dp[i][j]) {
return s.substring(j, j + i + 1);
}
}
}
return "";
}
}
中心扩展法
public class MyCenterExternSolution {
public String longestPalindrome(String s) {
if(s == null || s.length() == 0) {
return "";
}
if(s.length() == 1) {
return s;
}
int max_m = 0;
int max_n = 0;
int max = 0;
for(int i = 1; i < s.length() * 2; i++) {
int m,n,len=0;
if((i & 1) == 0) {
// i是偶数，说明中心点在一个字母上
m = i / 2;
n = i / 2;
} else {
// i是奇数，说明中心点在字母之间
m = (i - 1) / 2;
n = (i + 1) / 2;
}
while(m >= 0 && n < s.length() && s.charAt(m) == s.charAt(n)) {
m--;
n++;
len = n - m;
}
if(len > max) {
max = len;
max_m = m+1;
max_n = n-1;
}
}
return s.substring(max_m, max_n + 1);
}
}
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/76275.html
摘要：一题目最长回文子串给定一个字符串，找到中最长的回文子串。你可以假设的最大长度为。示例输入输出注意也是一个有效答案。 一、题目 最长回文子串： 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例 1： 输入: babad输出: bab注意: aba 也是一个有效答案。 示例 2： 输入: cbbd输出: bb 二、我的答案 思路 1.排...
摘要：贪心算法每一步必须满足一下条件可行的即它必须满足问题的约束。四题目分析贪心算法，总是做出在当前看来是最好的选择，不从整体最优上加以考虑，也就是说，只关心当前最优解，按照贪心策略，不关心以后，我们只关心当前利益。 一、写在前面 为什么要在LeetCode刷题？大家都知道不管是校招还是社招算法题是必考题，而这一部分恰巧是大多数人的短板，所以刷题首先是为了提高自身的编程能力，能够在算法面试中...
摘要：每天会折腾一道及以上题目，并将其解题思路记录成文章，发布到和微信公众号上。三汇总返回目录在月日月日这半个月中，做了汇总了数组知识点。或者拉到本文最下面，添加的微信等会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。 LeetCode 汇总 - 2019/08/15 Create by jsliang on 2019-08-12 19:39:34 Recently...
摘要：第一种方法常规方法。如果不存在公共前缀，返回空字符串。注意假设字符串的长度不会超过。说明本题中，我们将空字符串定义为有效的回文串。示例输入输出一个可能的最长回文子序列为。数值为或者字符串不是一个合法的数值则返回。 说明 本文作者：wwwxmu 原文地址:https://www.weiweiblog.cn/13s... 作者的博客站点：https://www.weiweiblog.c...
摘要：用将子字符串转化为，参见和的区别然后用动规方法表示字符串的前位到包含方法的个数。最后返回对应字符串末位的动规结果。 Problem A message containing letters from A-Z is being encoded to numbers using the following mapping: A -> 1 B -> 2 ... Z -> 26 Given ...
阅读 1846·2021-11-25 09:43
阅读 3688·2021-11-24 10:32
阅读 1076·2021-10-13 09:39
阅读 2328·2021-09-10 11:24
阅读 3344·2021-07-25 21:37
阅读 3464·2019-08-30 15:56
阅读 858·2019-08-30 15:44
阅读 1449·2019-08-30 13:18
