LeetCode之“字符串”：最短回文子串

　　题目要求：　

　　Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

　　For example:

　　Given "aacecaaa", return "aaacecaaa".

　　Given "abcd", return "dcbabcd".

　　这道题用暴力破解是无法通过LeetCode上的测试的。

　 1. 法一（暴力破解）

　　超过时间！！！！

 1 int findCenter(string s)
 2 {
 3     int center = 0;
 4     int szS = s.size();
 5     for (int i = 1; i < szS; i++)
 6     {
 7         int k = 1;
 8         while (k <= i && k < szS - i)
 9         {
10             if (s[i - k] != s[i + k])
11                 break;
12             k++;
13         }
14         if (i - k == -1 && i > center)
15             center = i;
16     }
17     return center;
18 }
19 
20 string char2String(char c)
21 {
22     stringstream ss;
23     string s;
24     ss << c;
25     ss >> s;
26     return s;
27 }
28 
29 string shortestPalindrome(string s) {
30     // clear spaces
31     if (s.front() == ' ')
32         s.erase(0, 1);
33     if (s.back() == ' ')
34         s.pop_back();
35 
36     string ret;
37     int szS = s.size();
38     if (szS == 0)
39         ret = "";
40     else if (szS == 1)
41     {
42         s += s;
43         ret = s;
44     }
45     else
46     {
47         ret = s;
48         int center = findCenter(s);
49         int left = center;
50         int right = center + left + 1;
51         if (szS - center - 1 > center && s[center] == s[center + 1])
52         {
53             right = szS;
54         }
55         for (int i = right; i < szS; i++)
56         {
57             ret.insert(0, char2String(s[i]));
58         }
59     }
60 
61     return ret;
62 }

View Code

　 2. 法二（暴力破解）

　　法二思路来源：How to get the shortest palindrome of a string。重要语句摘录如下：

　　Just append the reverse of initial substrings of the string, from shortest to longest, to the string until you have a palindrome. e.g., for "acbab", try appending "a" which yields "acbaba", which is not a palindrome, then try appending "ac" reversed, yielding "acbabca" which is a palindrome.

　　法二相对法一来说更加简单容易理解，但同样超过时间！！！！

 1 bool isPalindrome(string  s)
 2 {
 3     int szS = s.size();
 4     for (int i = 0; i < szS / 2; i++)
 5     {
 6         if (s[i] != s[szS - i - 1])
 7             return false;
 8     }
 9     return true;
10 }
11 
12 string shortestPalindrome(string s)
13 {
14     // clear spaces
15     if (s.front() == ' ')
16         s.erase(0, 1);
17     if (s.back() == ' ')
18         s.pop_back();
19     // 
20     string ret;
21     int szS = s.size();
22     if (szS == 0)
23     {
24         ret = "";
25     }
26     else if (szS == 1)
27     {
28         s += s;
29         ret = s;
30     }
31     else if (isPalindrome(s))
32     {
33         ret = s;
34     }
35     else
36     {
37         for (int i = 0; i < szS; i++)
38         {
39             string tmpStr = s;
40             for (int j = szS - i - 1; j < szS; j++)
41                 tmpStr.insert(tmpStr.begin(), s[j]);
42 
43             if (isPalindrome(tmpStr))
44             {
45                 ret = tmpStr;
46                 break;
47             }
48         }
49     }
50     return ret;
51 }

View Code

　　看来只能另寻他法了。。。。

　 3. 法三

　　法三参考自C++ 8 ms KMP-based O(n) time & O(n) memory solution，利用了KMP的思想。具体程序如下：

 1 class Solution {
 2 public:
 3     string shortestPalindrome(string s)
 4     {
 5         string rev_s(s);
 6         reverse(rev_s.begin(), rev_s.end());
 7         string combine = s + "#" + rev_s;   // 防止在匹配的时候，不从‘#’后开始
 8     
 9         int sz = combine.size();
10         vector<int> match(sz, 0);
11         int k = 0;
12         for (int i = 1; i < sz; i++) {
13             while (k > 0 && combine[i] != combine[k])
14                 k = match[k - 1];
15     
16             if (combine[i] == combine[k])
17                 k = k + 1;
18     
19             match[i] = k;
20         }
21         
22         return rev_s.substr(0, s.size() - match[sz - 1]) + s;
23     }
24 };

　　上边程序可以解释如下：

　　对构造的字符串combine进行匹配操作后，得到如下结果：

　　匹配部分也就是s和rev_s重复的部分，而不匹配的部分就是它们不一样的部分。接下来的字符串拼接操作就是：

　　拼接完成后即是最终的结果。