PAT 解题报告 1040. Longest Symmetric String (25)

1040. Longest Symmetric String 题目描述:

Given a string, you are supposed to output the length of the longest symmetric sub-string. For example, given “Is PAT&TAP symmetric?”, the longest symmetric sub-string is “s PAT&TAP s”, hence you must output 11.

PAT 解题报告 1040. Longest Symmetric String (25): 经典题目, 求字符串的最长回文子串, 使用动态规划方程(DP)求解, 复杂度是O(N^2)

1040. Longest Symmetric String 算法分析:

这个题目嘛, 方法太多了. 即使同一个思路的动态规划都有好几个版本的递归方程可以写. 具体有这些方法:

(1) 暴力法, 枚举所有的子串, 检测每一个子串是否是回文, 检测回文需要O(N)时间, 总共有O(N^2)个子串, 总时间O(N^3), 肯定超时

(2) 动态规划(DP), 考虑到暴力法中浪费时间的是回文的检测, 如果能在常数时间内检测回文, 那么就可以把时间复杂度降到O(N^2), 事实上这个也是可以做到的, 用一个数组isSymmetric[i][j]表示子串str[i, …, j]是不是回文, 那么判断子串str[i-1, …, j+1]是不是回文就可以通过检测str[i-1] == str[j+1]以及之间看isSymmetric[i][j]就可以在常数时间内搞定了. 总的时间复杂度O(N^2)

(3) 动态规划, 但是使用不一样的递归公式. 设dp[i][j]表示字符串str[i, …, j]的最长回文的长度, 考虑str[i] == str[j] or not 那么就有基本的递归式

dp[i][j] = max(dp[i][j-1], dp[i+1][j], dp[i+1][j-1])

下面是可以AC的代码:

#include <iostream>
#include <fstream>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>

#define REP(i,n) for(int i=0;i<(n);++i)

using namespace std;
int dp[1002][1002];

int max3(int a, int b, int c) {
    return max(max(a, b), c);
}

int gao(string &s, int start, int end) {
    if(start == end) return 1;
    if(start > end) return 0;

    if(dp[start][end] != -1) return dp[start][end];

    if(s[start] == s[end]) {
        dp[start+1][end-1] = gao(s, start+1, end-1);
        dp[start+1][end] = gao(s, start+1, end);
        dp[start][end-1] = gao(s, start, end-1);

        if(dp[start+1][end-1] == end-start-1)
            return dp[start][end] = 2 + dp[start+1][end-1];
        else
            return dp[start][end] = max3(dp[start+1][end-1], dp[start+1][end], dp[start][end-1]);
    }
    else {
        return dp[start][end] = max(dp[start+1][end] = gao(s, start+1, end),
                                    dp[start][end-1] = gao(s, start, end-1));
    }
    return -1;
}

int main(void) {
    string s;
    getline(cin, s);
    REP(i, 1002) REP(j, 1002) dp[i][j] = -1;
    cout<<gao(s, 0, s.size()-1)<<endl;
    return 0;
}

(4) 线性算法, 这个嘛, 比较高级, 没做过题目的话肯定想不到的, 这里不多介绍, 可以参考我的另一篇“leetcode: Longest Palindromic Substring

1040. Longest Symmetric String 注意点:

有些人可能会直接用longest common substring的方法去套, 也就是说原字符串S, S的reverse是S’, 那么找到S和S’的最长的公共子串就是原字符串S的最长回文子串, 这个是不对的, 比如 e.g., S = abcxdcba  S’ = abcdxcba , 显然最长公共子串是abc或者cba, 但是这个显然不是回文子串, 这里的问题出在公共子串对应的index是不一致的, 一定要通过寻找公共子串来找回文的话, 那么要对这个公共子串对应到原字符串上的index一致性做一点限制, 稍做修正的话, 也是可以做的, 请参考: “leetcode: Longest Palindromic Substring

总结

PAT 解题报告 1040. Longest Symmetric String (25): 经典题目, 求字符串的最长回文子串, 使用动态规划方程(DP)求解, 复杂度是O(N^2)

Written on January 5, 2014