最长回文字串

2021-02-28

5. 最长回文子串

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

给你一个字符串 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 仅由数字和英文字母（大写和/或小写）组成

枚举回文中心

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

有奇数个字符的字符串的回文判断第一步需要判断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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。