Leetcode5.最长回文子串

  • 时间:
  • 来源:互联网
  • 文章标签:

5:最长回文子符串

    • 题目
    • 思路一
    • 思路二

题目

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

示例 1:

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

示例 2:

输入: “cbbd”
输出: “bb”

思路一

这道题可以采用动态规划的方法,设置dp[i][j]表示字符串s(i....j)是否为回文子串,关键点在于:

  1. 初始条件:dp[i][i] = true;
  2. 状态转移方程:
    • s[i] == s[j]为false,则其必然不是回文子串,dp[i][j] = false
    • s[i] == s[j]为true,则需要考虑s(i+1....j-1)是否为回文子串,分为三种情况:当i+1=j,即两个字符相邻,此时返回true;当i+2=j,即两个字符中间还有一个字符,由于单个字符是回文字符,则其必然为回文字符,返回true;i + 2 < j时,即两个字符之间至少有两个字符,则dp[i][j] = dp[i+1][j-1]注意:此时还需考虑是否更新最长回文子串的长度和开始位置
      由上述可得回文字符串的长度和开始位置,利用字符串的函数即可输出返回值——String.substring(start, end),左闭右开。
class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        //Step1:判断特殊情况
        if(len < 2) return s;

        //Step2:辅助变量的设置
        char[] charArray = s.toCharArray();
        int maxLen = 1, start = 0 ;//分别表示最长回文子串开始下标,结束下标,长度
        boolean[][] dp = new boolean[len][len];//存储dp[i][j]是否为回文串

        //Step3:初始化对角线
        for(int i = 0; i < len; i++){
            dp[i][i] = true;//对角线
        }
        // Step4:两层循环,寻找上三角的dp值
        for(int j = 1; j < len; j++){
            for(int i = 0; i < j; i++){
                if(charArray[i] != charArray[j]){//这两个元素不相等,则直接返回false
                    dp[i][j] = false;
                }else{
                    if(j - i >= 3){//情况一:相等时,若两个字符不相邻,或者有超过一个字符时
                        dp[i][j] = dp[i + 1][j - 1];
                    }else{//情况二:相等时,若中间有一个字符或者没有字符,则其必然为true
                        dp[i][j] = true;
                    }
                }

                //更新maxLen和start
                if(dp[i][j] && maxLen < j - i + 1){
                    maxLen = j - i + 1;
                    start = i;
                }
            }
            
        }
        //Step5:返回结果
        return s.substring(start, start+maxLen);
    }
}

执行结果1
参考:动态规划

思路二

回文字符串长度是单数,则中心是一个字符;双数,则是一个字符与其相邻字符。因此可以从中心开始往两边扩展。

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        //Step1: 判断特殊情况
        if(len < 2) return s;
        //定义与结果有关的变量
        int start = 0, end = 0;

        //step2:一次循环遍历,每次都把该元素或者该元素与其相邻元素作为回文字符串的中心
        for(int i = 0; i < len ; i++){
            int len1 = expand(s, i, i);//回文字符串是单数,左右相等之后剩下中间一个元素
            int len2 = expand(s, i, i+1);//回文字符串是双数,中心两个严肃都相等
            int maxLen = Math.max(len1, len2);
            //判断是否更新与结果相关的变量
            if(maxLen > end - start){
                start = i - (maxLen - 1) / 2;
                end = i + maxLen / 2;
            }
        }
        //Step3:返回结果
        return s.substring(start, end+1);
    }

    private int expand(String s, int left, int right){
        int L = left, R = right;
        while(L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)){
            L--;R++;
        }
        //注意一定是R- L- 1,因为while循环中终止条件时,先是L--,R++
        return R - L - 1;
    }
}

执行结果2

本文链接http://www.taodudu.cc/news/show-83137.html