Code & Func

打卡，第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
bool isPalindrome(string &s,int first,int last){
2
    while(first < last && s[first] == s[last]){
3
        first++;
4
        last--;
5
    }
6
    if (first >= last) return true;
7
    else return false;
8
}
9
string longestPalindrome(string s) {
10
    int retF,retL;
11
    int l = longestPalindrome(s,0,s.size() -1 ,retF);
12
    return s.substr(retF,l);
13
}
14

15
int longestPalindrome(string &s,int first,int last,int &retF){
33 collapsed lines
16
    if (first < last){
17
        int lF,rF,mF;
18
        int mid = (first + last)/2;   //分
19
        //治
20
        int l = longestPalindrome(s,first,mid,lF);
21
        int r = longestPalindrome(s,mid + 1,last,rF);
22
        int ret = max(l,r);
23
        //合，已知
24
        int midMax = ret;
25
        for(int i = first;i <=mid ;i++)
26
            for(int j = mid + 1;j <= last;j++){
27
                if (j-i +1 > midMax && isPalindrome(s,i,j)){
28
                    midMax = j-i+1;
29
                    mF = i;
30
                }
31
            }
32
        if (midMax > ret){
33
            retF = mF;
34
            return midMax;
35
        } else if (ret == l){
36
            retF = lF;
37
        } else{
38
            retF = rF;
39
        }
40
        return ret;
41
    } else if (first == last ) {
42
        retF = first;
43
        return 1;
44
    } else {
45
        retF = first;
46
        return 0;
47
    }
48
}

大概的思路是：

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

然后是dicuss中的解法：

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

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