LeetCode 5. 最长回文子串
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |
🌈🌈😄😄
欢迎来到茶色岛独家岛屿本期将为大家揭晓LeetCode 5. 最长回文子串做好准备了么那么开始吧。
🌲🌲🐴🐴
一、题目名称
LeetCode 5. 最长回文子串
二、题目要求
给你一个字符串 s
找到 s
中最长的回文子串。
如果字符串的反序与原始字符串相同则该字符串称为回文字符串。
三、相应举例
示例 1
输入s = "babad"
输出"bab"
解释"aba" 同样是符合题意的答案。
示例 2
输入s = "cbbd"
输出"bb"
四、限制要求
1 <= s.length <= 1000
s
仅由数字和英文字母组成
五、解决办法
动态规划
1.定义二维数组dp[length][length]如果dp[left][right]为true则表示字符串从left到right是回文子串如果dp[left][right]为false则表示字符串从left到right不是回文子串。
2.如果dp[left+1][right-1]为true我们判断s.charAt(left)和s.charAt(right)是否相等如果相等那么dp[left][right]肯定也是回文子串否则dp[left][right]一定不是回文子串。
3.所以我们可以找出递推公式
dp[left][right]=s.charAt(left)==s.charAt(right)&&dp[left+1][right-1]
4.确定边界条件
如果s.charAt(left)=s.charAt(right)那么字符串从left到right是不可能构成子串的直接跳过即可。
如果s.charAt(left)==s.charAt(right)字符串从left到right能不能构成回文子串还需要进一步判断
如果left==right也就是说只有一个字符我们认为是回文子串。即dp[left][right]=trueleft==right
如果right-left<=2类似于"aa"或者"aba"我们认为是回文子串。即dp[left][right]=trueright-left<=2
如果right-left>2我们只需要判断dp[left+1][right-1]是否是回文子串才能确定dp[left][right]是否为true还是false。即dp[left][right]=dp[left+1][right-1]
六、代码实现
public static String longestPalindrome(String s) {
//边界条件判断
if (s.length() < 2)
return s;
//start表示最长回文串开始的位置
//maxLen表示最长回文串的长度
int start = 0, maxLen = 1;
int length = s.length();
boolean[][] dp = new boolean[length][length];
for (int right = 1; right < length; right++) {
for (int left = 0; left < right; left++) {
//如果两种字符不相同肯定不能构成回文子串
if (s.charAt(left) != s.charAt(right))
continue;
//下面是s.charAt(left)和s.charAt(right)两个
//字符相同情况下的判断
//如果只有一个字符肯定是回文子串
if (right == left) {
dp[left][right] = true;
} else if (right - left <= 2) {
//类似于"aa"和"aba"也是回文子串
dp[left][right] = true;
} else {
//类似于"a******a"要判断他是否是回文子串只需要
//判断"******"是否是回文子串即可
dp[left][right] = dp[left + 1][right - 1];
}
//如果字符串从left到right是回文子串只需要保存最长的即可
if (dp[left][right] && right - left + 1 > maxLen) {
maxLen = right - left + 1;
start = left;
}
}
}
//截取最长的回文子串
return s.substring(start, start + maxLen);
}