Code & Fun

打卡,第10天

今天刷的题是Longest Palindromic Substring,开始想着用动态规划做,但是我好像连动态规划是什么我都不知道。。。

题目:

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: “babad”

Output: “bab”

Note: “aba” is also a valid answer.
Example:

Input: “cbbd”

Output: “bb”

所以一如既往的想到了分治法:

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
bool isPalindrome(string &s,int first,int last){
while(first < last && s[first] == s[last]){
first++;
last--;
}
if (first >= last) return true;
else return false;
}
string longestPalindrome(string s) {
int retF,retL;
int l = longestPalindrome(s,0,s.size() -1 ,retF);
return s.substr(retF,l);
}

int longestPalindrome(string &s,int first,int last,int &retF){
if (first < last){
int lF,rF,mF;
int mid = (first + last)/2; //分
//治
int l = longestPalindrome(s,first,mid,lF);
int r = longestPalindrome(s,mid + 1,last,rF);
int ret = max(l,r);
//合,已知
int midMax = ret;
for(int i = first;i <=mid ;i++)
for(int j = mid + 1;j <= last;j++){
if (j-i +1 > midMax && isPalindrome(s,i,j)){
midMax = j-i+1;
mF = i;
}
}
if (midMax > ret){
retF = mF;
return midMax;
} else if (ret == l){
retF = lF;
} else{
retF = rF;
}
return ret;
} else if (first == last ) {
retF = first;
return 1;
} else {
retF = first;
return 0;
}
}

大概的思路是:

  • 先用分治法将问题规模不断减半,那么现在只需要考虑如何“合”了
  • 这里”合”的时间复杂度是O(n^2),没能找出更快的,嗯,不对,好像是O(n^3)….
  • whatever,这里的合就是用穷举法去做的,不过不知道为什么还是过了测试

然后是dicuss中的解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
string longestPalindrome(string s) {
if (s.empty()) return "";
if (s.size() == 1) return s;
int min_start = 0, max_len = 1;
for (int i = 0; i < s.size();) {
if (s.size() - i <= max_len / 2) break;
int j = i, k = i;
while (k < s.size()-1 && s[k+1] == s[k]) ++k; // Skip duplicate characters.
i = k+1;
while (k < s.size()-1 && j > 0 && s[k + 1] == s[j - 1]) { ++k; --j; } // Expand.
int new_len = k - j + 1;
if (new_len > max_len) { min_start = j; max_len = new_len; }
}
return s.substr(min_start, max_len);
}

emmm,这里好像也是用点穷举的感觉。


本文首发于Code & Fun