题目:
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
解题思路: 1、简单思路:暴力破解法,时间复杂度O(n^3),肯定通不过。
2、动态规划法:(一般含“最XX”等优化词义的题意味着都可以动态规划求解),时间复杂度O(n^2),空间复杂度O(n^2)。
形如"abba", "abbba"这样的字符串,如果用dp[i][j]表示从下标i到j之间的子字符串所构成的回文子串的长度,则有:
dp[i][j] = dp[i+1][j-1] && s[i] == s[j]
初始化:
奇数个字符:dp[i][i] = 1; 偶数个字符:dp[i][i+1] = 1
1 //动态规划法
2 string LongestPalindromicStringDP(string str)
3 {
4 size_t n = str.size();
5 if (n == 0 || n == 1)
6 return str;
7 //创建dp二维数组
8 //d[i][j] = dp[i+1][j-1] && s[i] == s[j]
9 bool **dp = new bool *[n];
10 for (size_t i = 0; i < n; ++ i)
11 dp[i] = new bool[n];
12
13 int nLongestIndex = 0; //最长回文子串的开始下标
14 int nMaxLen = 0; //长度
15
16 for (size_t i = 0; i < n; i ++)
17 for (size_t j = 0; j < n; j ++)
18 dp[i][j] = false;
19 for (size_t i = 0; i < n; ++ i)
20 dp[i][i] = true; //初始化一个字母
21
22 for (size_t i = 0; i < n - 1; ++ i) {
23 if (str[i] == str[i+1]) {
24 dp[i][i+1] = true; //初始化两个相同的字母"aa"
25 nLongestIndex = i;
26 nMaxLen = 2;
27 }
28 }
29 //从长度3开始操作, (aba)ba, a(bab)a, ab(aba)
30 for (size_t len = 3; len <= n; ++ len) {
31 for (size_t i = 0; i < n-len+1; ++ i) {
32 size_t j = i + len - 1;
33 if (str[i] == str[j] && dp[i+1][j-1]){
34 dp[i][j] = true;
35 nLongestIndex = i;
36 nMaxLen = len;
37 }
38 }
39 }
40
41 //释放dp
42 for (size_t i = 0; i < n; ++ i)
43 delete []dp[i];
44 delete []dp;
45
46 return str.substr(nLongestIndex, nMaxLen);
47 }
3、中心扩散法:时间复杂度O(n^2),空间复杂度O(1) 顾名思义,从一个节点,分别向两边扩散,用两个指针分别向前向后遍历。
1 //中心扩散法
2 string LongestPalindromicString(string str)
3 {
4 size_t n = str.size();
5 if (n == 0 || n == 1)
6 return str;
7
8 size_t start = 0;
9 size_t nMaxLen = 0;
10
11 for (size_t i = 0; i < n; ++ i) {
12 size_t j = i, k = i; //分别从中心向两边扩散
13 while(k < n-1 && str[k] == str[k+1])
14 k++; //有相同字母的情况:"aaa"
15 while(j > 0 && k < n-1 && str[j-1] == str[k+1]){
16 k++; //不同字母情况: "aba"
17 j--;
18 }
19 if(k-j+1 > nMaxLen){
20 nMaxLen = k-j+1;
21 start = j;
22 }
23 }
24 return str.substr(start, nMaxLen);
25 }
4、很明显,这两种方法时间复杂度还是太高了,还有一种算法叫Manacher,时间复杂度能够降为O(n),空间复杂度也为O(n),先记下,以后再做研究吧。