最长回文子串

2021-03-27

5. 最长回文子串

难度中等3421收藏分享切换为英文接收动态反馈

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

1
2
3

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

1 2	输入：s = "cbbd" 输出："bb"

示例 3：

1 2	输入：s = "a" 输出："a"

示例 4：

1 2	输入：s = "ac" 输出："a"

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成

动态规划只记录长度

import java.util.*;

public class Solution {
    public int getLongestPalindrome(String S, int n) {
        // write code here
        if(S==null||S.length()==0)return 0;
        boolean [][] f = new boolean[n][n];
        int max = 0;
        // 枚举子串的长度
        for(int k = 0;k<n;k++){
            // 枚举子串第一个字符的位置
            for(int i=0;i< n-k;i++){
                // j是子串第二个字符的位置
                int j = i+k;
                // 如果子串的长度等于1时,那么一定是回文的(1个字符是回文的)
                if(k==0){
                    f[i][j] = true;
                }else if(k==1){
                    // 如果子串的长度等于2并且两个字符是相同的那么他们是回文的,否则不是回文的
                    f[i][j]  = S.charAt(i)==S.charAt(j);
                }else{
                    // 当子串的长度大于2时,如果当前两个字符相同,要看左边界右移一个字符,右边界左移动一个字符的子串是不是回文的
                    // 如果两个条件都满足,那么说明当前的字符是回文的
                    f[i][j] = S.charAt(i)==S.charAt(j) & f[i+1][j-1]; 
                }
                // 记录回文字符的最大长度
                if(f[i][j])max =Math.max(max,k+1);
            }
        }
        return max;
    }
}

动态规划

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }
        int n=s.length();
        boolean dp[][]=new boolean[n+1][n+1];
        String ans="";
        // k枚举的是字符串的长度
        for(int k=0;k<n;k++){
            // i枚举的是第i个字母
            for(int i=0;i<n-k;i++){
                // i代表第i个字母
                // j代表第j个字母
                // dp[i][j]是从i到j之间的字符串是否是回文串
                // k是枚举的字符串的长度
                int j=i+k;
                if(k==0){
                    // k==0时，只有一个字符，一个字符是回文
                    dp[i][j]=true;
                }else if(k==1){
                    // k==1时有两个字符，只有当两个字符相等时，才有可能是回文
                    dp[i][j]=(s.charAt(i)==s.charAt(j));
                }else{
                    // i与j之间有多个字符的时候,当i和j相同时,i向右边移动一个位置,j向左边也移动一个位置,如果里面的也是回文,那么当前i与j之间也是回文
                    dp[i][j] = ((s.charAt(i)==s.charAt(j))&&dp[i+1][j-1]);
                }
                // 如果ij之间的字符串是回文的,并且当前的回文串的长度大于目前最大的回文串,那么更新最大的回文串
                if(dp[i][j]&&k+1>ans.length()){
                    ans=s.substring(i,i+k+1);
                }
            }
        }
        return ans;
    }
        
}

枚举回文中心

回文中心有两种情况，分别是有奇数个字符的回文字符串的回文中心和有偶数个字符的回文中心

有奇数个字符的字符串的回文判断第一步需要判断s.charAt(i)==s.charAt(i)

有偶数个字符的字符串的回文判断第一步需要判断s.charAt(i)==s.charAt(i+1)

因此每枚举一个index的时候需要进行两次判断

class Solution {
    public String longestPalindrome(String s) {
        int max=0;
        String ans="";
        int n = s.length();
		
        // 巧妙的避免奇数与偶数中心问题
        for (int i = 0; i < 2 * n - 1; ++i) {
            // "cbbd"
            // 如果是偶数，那么左右指针对应的index是相同的
            // 如果是奇数，那么左右指针对应的index是不同的
            // 因此会计算两遍，（0，0）（0，1）（1，1）（1，2）（2，2）（2，3）（3，3）
            // 每次计算相邻的
            int l = i / 2, r = i / 2 + i % 2;
            while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
                --l;
                ++r;
            }
            if(l!=i/2)l++;

            if(r-l+1>max){
                ans=s.substring(l,r);
                max=r-l+1;
            }
        }
        return ans;
    }
}

动态规划

外层枚举每个字符串的长度

内层枚举字符串中的每个字符

标记以每个字符为中心的满足回文串的字符，自回文中心向外扩充回文串的长度，并记录其中的最大子字符串

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        String ans = "";
        // 枚举子字符串的长度
        for (int l = 0; l < n; ++l) {
            // 枚举每个字符
            for (int i = 0; i + l < n; ++i) {
                int j = i + l;
                if (l == 0) {// 也就是dp[i][j]=true 一个字符自身肯定是回文的
                    dp[i][j] = true;
                } else if (l == 1) {// 相邻的两个字符是相同的那么这两个字符是回文的
                    dp[i][j] = (s.charAt(i) == s.charAt(j));
                } else {
                    // dp[i+1][j-1]其中i+1是向右移动左边界，j-1是向左移动右边界，即如果当前的相同并且靠近回文中心的也相同，那么i和j对应的也相同（需要自内而外计算）
                    dp[i][j] = (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]);
                }
                // 其中l是枚举的区间的长度
                if (dp[i][j] && l + 1 > ans.length()) {
                    ans = s.substring(i, i + l + 1);
                }
            }
        }
        return ans;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

枚举回文中心

回文中心有两种情况，分别是有奇数个字符的回文字符串的回文中心和有偶数个字符的回文中心

有奇数个字符的字符串的回文判断第一步需要判断s.charAt(i)==s.charAt(i)

有偶数个字符的字符串的回文判断第一步需要判断s.charAt(i)==s.charAt(i+1)

因此每枚举一个index的时候需要进行两次判断


class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            // 注意这个计算左右边界的代码,十分巧妙
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    public int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            --left;
            ++right;
        }
        return right - left - 1;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

manacher算法


class Solution {
    public String longestPalindrome(String s) {
        int start = 0, end = -1;
        StringBuffer t = new StringBuffer("#");
        for (int i = 0; i < s.length(); ++i) {
            t.append(s.charAt(i));
            t.append('#');
        }
        t.append('#');
        s = t.toString();

        List<Integer> arm_len = new ArrayList<Integer>();
        int right = -1, j = -1;
        for (int i = 0; i < s.length(); ++i) {
            int cur_arm_len;
            if (right >= i) {
                int i_sym = j * 2 - i;
                int min_arm_len = Math.min(arm_len.get(i_sym), right - i);
                cur_arm_len = expand(s, i - min_arm_len, i + min_arm_len);
            } else {
                cur_arm_len = expand(s, i, i);
            }
            arm_len.add(cur_arm_len);
            if (i + cur_arm_len > right) {
                j = i;
                right = i + cur_arm_len;
            }
            if (cur_arm_len * 2 + 1 > end - start) {
                start = i - cur_arm_len;
                end = i + cur_arm_len;
            }
        }

        StringBuffer ans = new StringBuffer();
        for (int i = start; i <= end; ++i) {
            if (s.charAt(i) != '#') {
                ans.append(s.charAt(i));
            }
        }
        return ans.toString();
    }

    public int expand(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            --left;
            ++right;
        }
        return (right - left - 2) / 2;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。