【Check 81】2024-05-23 - 5. 最长回文子串

[larscheng]

5. 最长回文子串

[larscheng]

思路

中心位置展开 回文串分为奇数串和偶数串

• 奇数串：可以把每一个字符作为回文串的中心位置向两边扩展，i(i,i),单独字符也是回文串
• 偶数串：可以把两个字符中的间隙作为回文串中心向两边扩展，i(i,i+1)

  当left>=0&&right<s.length&&s[left]==s[right]时，回文串的长度为right-left-1

代码

class Solution {
    /**
     * 中心展开
     */
    public String longestPalindrome(String s) {
        if (s == null || s.isEmpty()) {
            return null;
        }
        if (s.length()==1){
            return s;
        }
        int start=0,end=0;
        int maxLen = 0;
        for (int i = 0; i < s.length(); i++) {
            //奇数串，从当前位置为中心
            int len1 = expandCenter(s,i,i);
            //偶数串，从当前位置的间隙为中心
            int len2 = expandCenter(s,i,i+1);
            maxLen = Math.max(len1,len2);
            //maxLen > end - start 表示只记录首个最长回文串
            //maxLen > end - start+1 表示只记录最后一个最长回文串
            if (maxLen > end - start+1) {
                start = i-(maxLen-1)/2;
                end = i+maxLen/2;
            }
        }
        return s.substring(start, end + 1);
    }
    private int expandCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        // 1-(-1)-1 = 1
        return right - left - 1;
    }
}

复杂度

• 时间复杂度：O(n*n)
• 空间复杂度：O(1)

[larscheng]

思路

动态规划

串aba是回文串，cabac也一定是回文串

• dp[i][j]表示字符串s[i:j]是否是回文串
• 字符串s[i:j]的长度为len=j-i+1
• 如果len<=2,dp[i][j] = (s[i]==s[j])
• 如果len >2,dp[i][j] = (s[i]==s[j]) && dp[i+1][j-1]

代码

class Solution {
    /**
     * 动态规划
     */
    public String longestPalindrome(String s) {
        if (s == null || s.isEmpty()) {
            return null;
        }
        if (s.length()==1){
            return s;
        }
        int start=0;
        int maxLen = 0;
        boolean[][] dp = new boolean[s.length()][s.length()];

        for (int i = s.length()-1; i >=0 ; i--) {
            for (int j = i; j < s.length() ; j++) {
                int len = j-i+1;
                //如果len<=2,dp[i][j] = (s[i]==s[j])
                //如果len >2,dp[i][j] = (s[i]==s[j]) && dp[i+1][j-1]
                dp[i][j] = (s.charAt(i)==s.charAt(j)) && (len <= 2 || dp[i + 1][j - 1]);
                if (dp[i][j] && len > maxLen) {
                    maxLen = len;
                    start = i;
                }
            }
        }
        return s.substring(start, start + maxLen);
    }
}

复杂度

O(n*n)/O(n*n)

[larscheng]

中心扩展更简洁，更容易理解的版本

    public String longestPalindrome(String s) {
        String res = "";

        for (int i = 0; i < s.length(); i++) {
            String s1 = findStr(s,i,i);
            String s2 = findStr(s,i,i+1);
            res = res.length()>s1.length()?res:s1;
            res = res.length()>s2.length()?res:s2;
        }
        return res;
    }

    private String findStr(String s, int left, int right) {
        //找到回文串之后，会继续扩展，如果下一个不是回文串，结束while
        while (left>=0&&right<=s.length()-1&&s.charAt(left)==s.charAt(right)) {
            left--;
            right++;
        }
        //结束while之前上一轮是回文串left+1，substring左闭右开，right不用-1
        return s.substring(left+1, right);
    }