leetcode 05 回笔墨符串
leetcode 05 回笔墨符串1. 形貌
给你一个字符串，找到里面最长的回笔墨符串
2. 事例
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
3. 思路
3.1 什么是回笔墨串
abba
abcba
我们把这种不管是从前到后读还是从后到前读都是一样的单词叫做回笔墨串
3.2 思路
3.2.1 dp数组
明确一个dp数组，即当前dp数组每个下标对应的含义
dp 表示s的前i个字符到j个字符是否符合回文字串。
字符串ábcba下标01234 i/j012340TrueFalseFalseFalseTrue1TrueFalseTrueFalse2TrueFalseFalse3TrueFalse4True 3.2.2 怎么判定当前子串是回笔墨串。
d p [ i ] [ j ] = s [ i ] = = s [ j ] a n d s [ i + 1 ] [ j − 1 ] o r j − 1 < = 2 dp = s == s and s or j - 1 <= 2 dp=s==sandsorj−1<=2
假设我现在有个字符串aba
当s和s等于当时间，我们就需要判定从i到j里面包罗了几个字符。
比如当i = 0 j = 2当是时间，如果s = s 就只需要判定里面的元素是否大于1了，我们就可以得到一个公式。
j − i < = 2 j - i <= 2 j−i<=2
如果这个公式成立的话，而且s = s 那么就是一个回笔墨串。
只需要判定s == s 而且 s 大概 j - i <= 2。
3.3.3 怎么取最大的回笔墨串。
我们上面知道了怎么判定字串是回笔墨串，我们就可以先定义一个left，并记录一个最大的长度。然后每次是回笔墨串的时间判定是否大于已经记录的，如果大于则就进行替换，如果小宇我们就跳过。
注意！！！ 这里我们要注意下。
这里的最大长度应该好似j - i + 1.
3.3.4 代码编写
3.3.4.1 python
def longestPalindrome(s: str) -> str:
if len(s) <= 1:
return s
left = 0
maxLength = 1
dp = [ for i in range(len(s))]
for j in range(1, len(s)):
for i in range(j):
if s != s:
continue
else:
dp = dp or j - i <= 2
if dp and j - i + 1 > maxLength:
left = i
maxLength = j - i + 1
return s
3.3.4.2 typescript
onst longestPalindrome = (s: string): string => {
if (s.length <= 1) return s;
let left = 0, maxlength = 1;
const dp = new Array(s.length).fill(0).map(item => new Array(s.length).fill(false));
for (let j = 1; j < s.length; j++) {
for (let i = 0; i < j; i++) {
if (s !== s) continue;
dp = dp || j - i <= 2;
if (dp && j - i + 1 > maxlength) {
maxlength = j - i + 1;
left = i;
}
}
}
return s.slice(left, left + maxlength)
}
java
public static String longestPalindromeV2(String s) {
int left = 0;
int maxLength = 1;
boolean[][] dp = new boolean;
if (s.length() <= 1) return s;
for (int j = 1; j < s.length(); j++) {
for (int i = 0; i < j; i++) {
if (s.charAt(i) != s.charAt(j)) {
continue;
} else {
dp = dp || j - i <= 2;
}
if (dp && j - i + 1 > maxLength) {
maxLength = j - i + 1;
left = i;
}
}
}
return s.substring(left, left + maxLength);
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]