5. 最长回文子串

发表评论
363 views

 ›
5. 最长回文子串

官方链接

https://leetcode-cn.com/problems/longest-palindromic-substring/

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

思路

  1. 暴力 O(n^3) 嵌套循环, 枚举 i, j (起点和终点), 判断字串是否回文

  2. 中间向两边扩张法 O(n^2)

  3. 动态规划

    首先定义 dp[i][j]: dp[i][j] = true 是回文串

接下来

'''
dp[i][j] 表示子串从 i 到 j 是否是回文子串
如果 dp[i+1][j-1] 为回文，且 s[i] == s[j]，则 dp[i][j] 为回文
dp 对角线上的都是回文
只有两个字符为回文
'''
if i == j:
    dp[i][j] = True
if i+1 == j:
    dp[i][j] = s[i] == s[j]
if  i+1 < j:
    dp[i][j] = s[i] == s[j] and dp[i+1][j-1]

解法一

动态规划

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        String res = "";

        boolean[][] dp = new boolean[n][n]; 

        for (int i = n - 1; i >=0; i--) { // 第一层循环枚举回文子串的起点
            for (int j = i; j <= n - 1; j++) { // 第二层循环枚举回文子串的终点

                dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1]); 
                if (dp[i][j] && j - i + 1 > res.length()) {
                    res = s.substring(i, j + 1);
                }
            }
        }
        return res;
    }
}

解法二

class Solution {

    private int lo, maxLen;
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) return s;

        for (int i = 0; i < len - 1; i++) {
            extendPalindrome(s, i, i); // odd length
            extendPalindrome(s, i, i+1);
        }

        return s.substring(lo, lo + maxLen);
    }

    private void extendPalindrome(String s, int j, int k) {
        while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
            j--;
            k++;
        }
        if (maxLen < k - j - 1) {
            lo = j + 1;
            maxLen = k - j - 1;
        }
    }
}