leetcode 05 回笔墨符串

leetcode 05 回笔墨符串

1. 形貌

给你一个字符串，找到里面最长的回笔墨符串
2. 事例

示例 1：

1. 输入：s = "babad"
2. 输出："bab"
3. 解释："aba" 同样是符合题意的答案。

复制代码

示例 2：

1. 输入：s = "cbbd"
2. 输出："bb"

复制代码

3. 思路

3.1 什么是回笔墨串

1. abba
2. abcba

复制代码

我们把这种不管是从前到后读还是从后到前读都是一样的单词叫做回笔墨串
3.2 思路

3.2.1 dp数组

明确一个dp数组，即当前dp数组每个下标对应的含义

1. dp[i][j] 表示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[j] = s == s[j] and s[i+1][j-1] or j - 1 <= 2                     dp[j]=s==s[j]ands[i+1][j−1]orj−1<=2
假设我现在有个字符串aba
当s和s[j]等于当时间，我们就需要判定从i到j里面包罗了几个字符。
比如当i = 0 j = 2当是时间，如果s = s[j] 就只需要判定里面的元素是否大于1了，我们就可以得到一个公式。
                                         j                            −                            i                            <                            =                            2                                  j - i <= 2                     j−i<=2
如果这个公式成立的话，而且s = s[j] 那么就是一个回笔墨串。
只需要判定s == s[j] 而且 s[i + 1] [j - 1] 大概 j - i <= 2。
3.3.3 怎么取最大的回笔墨串。

我们上面知道了怎么判定字串是回笔墨串，我们就可以先定义一个left，并记录一个最大的长度。然后每次是回笔墨串的时间判定是否大于已经记录的，如果大于则就进行替换，如果小宇我们就跳过。
注意！！！ 这里我们要注意下。
这里的最大长度应该好似j - i + 1.
3.3.4 代码编写

3.3.4.1 python

1. def longestPalindrome(s: str) -> str:
2.     if len(s) <= 1:
3.         return s
4.     left = 0
5.     maxLength = 1
6.     dp = [[False for i in range(len(s))] for i in range(len(s))]
7.     for j in range(1, len(s)):
8.         for i in range(j):
9.             if s[i] != s[j]:
10.                 continue
11.             else:
12.                 dp[i][j] = dp[i + 1][j - 1] or j - i <= 2
13.             if dp[i][j] and j - i + 1 > maxLength:
14.                 left = i
15.                 maxLength = j - i + 1
16.     return s[left: left + maxLength]

复制代码

3.3.4.2 typescript

1. onst longestPalindrome = (s: string): string => {
2.     if (s.length <= 1) return s;
3.     let left = 0, maxlength = 1;
4.     const dp = new Array(s.length).fill(0).map(item => new Array(s.length).fill(false));
5.     for (let j = 1; j < s.length; j++) {
6.         for (let i = 0; i < j; i++) {
7.             if (s[i] !== s[j]) continue;
8.             dp[i][j] = dp[i + 1][j - 1] || j - i <= 2;
9.             if (dp[i][j] && j - i + 1 > maxlength) {
10.                 maxlength = j - i + 1;
11.                 left = i;
12.             }
13.         }
14.     }
15.     return s.slice(left, left + maxlength)
16. }

复制代码

java

1. public static String longestPalindromeV2(String s) {
2.         int left = 0;
3.         int maxLength = 1;
4.         boolean[][] dp = new boolean[s.length() + 1][s.length() + 1];
5.         if (s.length() <= 1) return s;
6.         for (int j = 1; j < s.length(); j++) {
7.             for (int i = 0; i < j; i++) {
8.                 if (s.charAt(i) != s.charAt(j)) {
9.                     continue;
10.                 } else {
11.                     dp[i][j] = dp[i + 1][j - 1] || j - i <= 2;
12.                 }
13.                 if (dp[i][j] && j - i + 1 > maxLength) {
14.                     maxLength = j - i + 1;
15.                     left = i;
16.                 }
17.             }
18.         }
19.         return s.substring(left, left + maxLength);
20.     }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。