算法练习——最长回文子串

今日练习完成后,真的很不甘心,遇到什么都做不出来,决定来回顾这道卡了我一个月的题目,5. 最长回文子串,这题最开始一直有一些小细节没有思考到位,每次失败后都去尝试理解题解,终于在今天不靠题解想出了解答方法,首先用递归的思想,这个方法就完成匹配,如果是回文,就返回,不是回文就接着递归,直到这个字符串切割完,这个方法是超出限制时间的,然后将递归拍平就通过了,具体代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public String longestPalindrome(String s) {
String longest = "";
int length = s.length();
for (int i = 0; i < length; i++) {
String l = longest(s.substring(i, length), length - i - 1);
if (l.length() > longest.length()) {
longest = l;
}
}
return longest;
}

public String longest(String s, int end) {
char[] array = s.toCharArray();
int left = 0, right = end;
while (left <= right && !s.isEmpty()) {
if (array[left++] != array[right--]) {
// return longest(s.substring(0, end), end - 1);
s = s.substring(0, end);
end--;
left = 0;
right = end;
}
}
return s;
}
}

平时练习的比较少,这两天的每日一题有点难度,有点想弃坑了,但是突然就想来再练习一题,就打开了这道万恶的回文字符串,然后就想到可以使用递归的思想去解决,然后尝试了半个小时完成了递归的解答,然后发现这个递归可以拍平,于是就解答出来了,时间复杂度刚好擦着边通过了。这道题解决了,满血复活,明天继续完成每日一题挑战,算法这条路虽然坎坷,但是相信有一天能够铺好一条属于自己的平坦的道路。