最长回文子串（c++）

1、暴力解法时间O(n^3) 空间O(1)

string longestPalindrome(string s) {
    int len = s.length();
    if (len < 2) {
        return s;
    }
    int maxn = 1;
    int idx = 0;
    for (int i = 1; i < len - 1; i++) {
        for (int j = i + 1; j < len; j++) {
            string tmp = s.substr(i, j - i + 1);
            string tmp2 = tmp;
            reverse(tmp.begin(), tmp.end());
            if (tmp == tmp2 && j - i + 1 > maxn) {
                maxn = j - i + 1;
                idx = i;
            }
        }
    }
    return s.substr(idx, maxn);
}

2、动态规划时间O(n^2) 空间O(n^2)

边界条件

• 当子串长度为1时，dp[i][i] = true
• 当子串长度为2时，dp[i][j] = s[i]==s[j]

动态转移方程

• dp[i][j] = dp[i+1][j-1] && s[i] == s[j]

string longestPalindrome(string s) {
    int len = s.length();
    if (len < 2) {
        return s;
    }
    int maxn = 1;
    int idx = 0;
    vector<vector<int> > dp(len, vector<int>(len));
    for (int i = 0; i < len; i++) {
        dp[i][i] = 1;
    }
    for (int j = 1; j < len; j++) {
        for (int i = 0; i < j; i++) {
            if (s[i] != s[j]) {
                dp[i][j] = 0;
            }
            else
            {
                if (j - i + 1 < 4) 
                    dp[i][j] = 1;
                else
                    dp[i][j] = dp[i + 1][j - 1];
            }

            if (dp[i][j] && j - i + 1 > maxn) {
                maxn = j - i + 1;
                idx = i;
            }
        }
    }
    return s.substr(idx, maxn);
}

3、中心扩展时间O(n^2) 空间O(1)

以下标 i 表示的字符为中心点向两端扩展，判断扩展后的字符是否为回文串

• 回文子串长度为奇数，中心为s[i]
• 回文子串长度为偶数，中心为s[i, i+1]

string longestPalindrome(string s) {
    int len = s.length();
    if (len < 2) {
        return s;
    }
    int maxn = 1;
    int idx = 0;

    for (int i = 0; i < len - 1; i++) {
        int oddLen = computeLen(s, i, i);
        int evenLen = computeLen(s, i, i + 1);
        int tempLen = max(oddLen, evenLen);
        if (tempLen > maxn) {
            maxn = tempLen;
            idx = i - (tempLen - 1) / 2;
        }
    }
    return s.substr(idx, maxn);
}

int computeLen(string s, int l, int r) {
    int len = s.length();
    int i = l, j = r;
    while (i >= 0 && j < len) {
        if (s[i] == s[j]) {
            i--; j++;
        }
        else
        {
            break;
        }
    }
    return j - i - 1;
}

原文链接: https://www.cnblogs.com/cicinnus/p/13227577.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍