力扣5
https://leetcode-cn.com/problems/longest-palindromic-substring/
思路
很有意思很高频的一道题，我的思路历程是这样的：
确定左右然后对区间判断？ 不对—>应该是以i为中间往两边扩散
“aba”和”abba”好像不一样啊？ 只是l和r初始值不能是等于i，而是相同字母的左右边界，这样两种情况就一样了
想明白了这两点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public String longestPalindrome(String s) {
if (s == null || s.length() == 0) return "";
char[] chars = s.toCharArray();
int[] idx = new int[2];
for (int i = 0; i < chars.length; i++) {
int l = i, r = i;
while (l - 1 >= 0 && chars[l - 1] == chars[i]) l--;
while (r + 1 < chars.length && chars[r + 1] == chars[i]) r++;
while (l - 1 >= 0 && r + 1 < chars.length){
if (chars[l - 1] != chars[r + 1]){
break;
}
l--;
r++;
}
if ((r - l) > (idx[1] - idx[0])){
idx[0] = l;
idx[1] = r;
}
}
return s.substring(idx[0], idx[1] + 1);
}
|
优化
[a]代表当前遍历到了哪里
对于b[b]bbb和 bb[b]bb我们可以发现其实定位l和r的初始值后是一样的，所以我们可以跳过这几种，具体有以下两点要做
- 定位完r后，直接让i = r，跳过中间的所有b（[b]bbbb—>bbbb[b]）
- 这样操作后实际上没有i在中间的情况（b[b]bbb），因为我们实际上只找了最左边那次，所以可以不用再定位l，只需要定位r
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public String longestPalindrome(String s) {
if (s == null || s.length() == 0) return "";
char[] chars = s.toCharArray();
int[] idx = new int[2];
for (int i = 0; i < chars.length; i++) {
int l = i, r = i;
while (r + 1 < chars.length && chars[r + 1] == chars[i]) r++;
i = r;
while (l - 1 >= 0 && r + 1 < chars.length){
if (chars[l - 1] != chars[r + 1]){
break;
}
l--;
r++;
}
if ((r - l) > (idx[1] - idx[0])){
idx[0] = l;
idx[1] = r;
}
}
return s.substring(idx[0], idx[1] + 1);
}
|
后记，准备将原来的一些题目重做一下，有一些题目真的是感觉得出一定是高频题，比如链表反转，最长回文，最长不重复，最大子数组…接下来会重做这些题目
参考
评论区糖丶7的方法
其他字符串类型的题目可以点击这里