最长回文子串
注意, substring和subsequence 是有区别的。substring属于subsequence, 但是subsequence 不一定是substring。
给定一个string T = str[0...n-1], 该字符串的一个子串substring就是截取连续的(包括全部)的一部分subT = [i, ...j], 其中, 0<= i and j <= n-1。 但是subsequence则是选择相关的字符, 保持其在原字符串中的相对顺序, 然后组成的新的string就是subsequence, 别混淆了。
最长回文子串(LPS)就是从给定的字符串中找出最长的一个子字符串, 这个子字符串从左往右读和从右往左读, 读出的结果是一样的。
例如:aba, a, abba均是回文子串。 在例如, S = "abcbcbb"的LPS 是“bcbcb”。
(方法一) bruteforce的办法: 最简单的办法就是价差字符串的每一个子字符串是否为palindrome or not。 我们可以运行三个loops, 外层两个loops 一个个的选择字符串所有可能的子字符串, 内层循环检查选的该子字符串是否是palindorme的。
- #include <string>
- #include <iostream>
- using namespace std;
- /*判断str[i..j]是否为回文串*/
- bool isPalindrome(string str, int Start, int End) {
- while(str[Start++] == str[End--] && Start <= End) { }
- if(str[--Start] != str[++End]) {
- return false;
- } else {
- return true;
- }
- }
- /*返回最长回文子串长度*/
- string longestPald(string str) {
- int len = str.length();
- int longest = 1;
- if(len == 1) {
- return str.substr(0, 1);
- }
- int longestStart = 0;
- for(int i = 0; i<len; i++) {
- for(int j = i + 1; j < len; j++) {
- if(isPalindrome(str, i, j)) {
- if(longest < j - i + 1) {
- longestStart = i;
- longest = j - i + 1;
- }
- //longest = (longest < j-i+1 ? j-i+1: longest);
- }
- }
- }
- cout << longest << endl;
- return str.substr(longestStart, longest);
- }
- int main() {
- string s = "forgeeksskeegfor";
- cout << longestPald(s) << endl;
- return 0;
- }
分析: 时间复杂度: O(n^3)
辅助空间复杂度: O(1)
(方法二) 动态规划的办法: 我们maintain一个boolean的table[n][n], 然后自底向上的方式填充这个table。 如果子字符串str[i, j]是palindrome的 我们就把table[i][j]记为true, 否则就记为false。 为了计算table[i][j], 我们需要首先检查table[i+1][j-1], 如果table[i+1][j-1]是true的, 并且str[i]与str[j]是相同的字符, 我们就记录table[i][j]为true。否则table[i][j]就为false。 更详细的分析见下面:
如果substring(i, j)是palindromic的, 那么substring(i+1, j-1)也是palindromic的。
table[i][j]是palindromic的, 那么几位true。 otherwise, 记为0。
当j - i 比较小的时候, 即为0或者为1, 那么我们很容易知道:
table[i][i] = true, table[i][i+1] = (S[i] == S[j]), 这是base case。
另外, 还有table[i][j] = table[i + 1] [j - 1] && S[i]==S[j]。
table[i][i]如下:
table[i][i+1]如下:
table[i][i+2], table[i][i+3]等等如下:
程序如下:
- #include <string>
- #include <cstring>
- #include <iostream>
- using namespace std;
- string longestPalindromeDP(string s) {
- int n = s.length();
- int longestBegin = 0;
- int maxLen = 1;
- bool table[1000][1000];
- memset(table, 0, sizeof(table[0][0]) * 1000 * 1000);
- // for substring of length 1 are palindrome
- for (int i = 0; i < n; i++) {
- table[i][i] = true;
- }
- //check for substring of length 2
- for (int i = 0; i < n-1; i++) {
- if (s[i] == s[i+1]) {
- table[i][i+1] = true;
- longestBegin = i;
- maxLen = 2;
- }
- }
- // check for lengths greater than 2
- // len is the length of substring
- for (int len = 3; len <= n; len++) {
- // fix the starting index
- for (int i = 0; i < n-len+1; i++) {
- int j = i+len-1;
- // checking for sub-string from ith index to
- // jth index iff str[i+1] to str[j-1] is a
- // palindrome
- if (s[i] == s[j] && table[i+1][j-1]) {
- table[i][j] = true;
- /*if(len > maxlen) { // 总是成立, 所以可以去掉这个条件
- longestBegin = i;
- maxLen = len;
- } */
- longestBegin = i;
- maxLen = len;
- }
- }
- }
- return s.substr(longestBegin, maxLen);
- }
- int main() {
- string s = "forgeeksskeegfor";
- cout << longestPalindromeDP(s) << endl;
- return 0;
- }
运行结果如下:
分析: 时间复杂度: O(n^2)
辅助空间复杂度: O(n^2) (其实还可以改进的, 使得改进后的空间复杂度为O(n))
(方法三)Manacher 算法, 时间复杂度为O(n)。
虽然很屌, 太耗时间了。 有时间在研究。 you are not expected to think such a good algorithms。
(方法四): (利用最长公共子序列求解) LPS 就是str和str反转过来的LCS, 我们只需要找出这两个字符串的LCS即可。 这又归结为动态规划的内容了。
(方法五): 观察到一个palindrome 是关于center 成镜像的。 例如 ab|ba, a b a, 注意palindrome为偶数个字符的时候,中心在两个字符之间, 当palindrome的字符个数为奇数的时候, 中心是在最中间的那个字符。
对于一个具有N个字符的字符串, 共有2N - 1 个centers。 因为两个字符之间也可能是center,字符本身也可能是center, 所以是2N - 1。 所以我们只需要对每个中心进行expand的方式查找palindrome, 每个中心需要花费O(N), 所以这个方法的时间复杂度是O(N^2)。
- string expandAroundCenter(string s, int c1, int c2) {
- int l = c1, r = c2;
- int n = s.length();
- while (l >= 0 && r <= n-1 && s[l] == s[r]) {
- l--;
- r++;
- }
- return s.substr(l+1, r-l-1);
- }
- string longestPalindromeSimple(string s) {
- int n = s.length();
- if (n == 0) return "";
- string longest = s.substr(0, 1); // a single char itself is a palindrome
- for (int i = 0; i < n-1; i++) {
- string p1 = expandAroundCenter(s, i, i);
- if (p1.length() > longest.length())
- longest = p1;
- string p2 = expandAroundCenter(s, i, i+1);
- if (p2.length() > longest.length())
- longest = p2;
- }
- return longest;
- }