美文网首页
LeetCode_05_最长回文子串

LeetCode_05_最长回文子串

作者: NWPU_HaiboWu | 来源:发表于2020-01-30 20:48 被阅读0次

    1.题目描述

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

    示例 1:
    输入: "babad"
    输出: "bab"
    注意: "aba" 也是一个有效答案。
    示例 2:
    输入: "cbbd"
    输出: "bb"

    2.思路分析与代码实现

    其实看到这个题,我最先联想到的是滑动窗口法,但仔细想想好像不太一样。


    方法一:动态规划

    我看到了动态规划算法:
    ① 思考状态
    状态先尝试“题目问什么,就把什么设置为状态”。然后考虑“状态如何转移”,如果“状态转移方程”不容易得到,尝试修改定义,目的仍然是为了方便得到“状态转移方程”。
    ② 状态转移方程
    技巧是分类讨论。对状态空间进行分类,思考最优子结构到底是什么。即大问题的最优解如何由小问题的最优解得到。

    动态规划的本质就是打表格,从一个小规模问题出发,逐步得到大问题的解,并记录过程。动态规划依然是“空间换时间”思想的体现。

    ③ 思考初始化

    初始化是非常重要的,一步错,步步错,初始化状态一定要设置对,才可能得到正确的结果。
    角度 1:直接从状态的语义出发;
    角度 2:如果状态的语义不好思考,就考虑“状态转移方程”的边界需要什么样初始化的条件;
    角度 3:从“状态转移方程”方程的下标看是否需要多设置一行、一列表示“哨兵”,这样可以避免一些边界的讨论,使得代码变得比较短。
    ④ 思考输出
    有些时候是最后一个状态,有些时候可能会综合所有计算过的状态。
    ⑤ 思考状态压缩
    “状态压缩”会使得代码难于理解,初学的时候可以不一步到位。先把代码写正确,然后再思考状态压缩。
    状态压缩在有一种情况下是很有必要的,那就是状态空间非常庞大的时候(处理海量数据),此时空间不够用,就必须状态压缩


    第 1 步:定义状态
    dp[i][j] 表示子串 s[i, j] 是否为回文子串。
    第 2 步:思考状态转移方程
    根据头尾字符是否相等做分类讨论,根据上面的分析得到:

    dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]

    分析这个状态转移方程:

    (1)“动态规划”事实上是在填一张二维表格,i 和 j 的关系是 i <= j ,因此,只需要填这张表的上半部分;

    (2)看到 dp[i + 1][j - 1] 就得考虑边界情况。

    边界条件是:表达式 [i + 1, j - 1] 不构成区间,即长度严格小于 2,即 j - 1 - (i + 1) + 1 < 2 ,整理得 j - i < 3。

    这个结论很显然:当子串 s[i, j] 的长度等于 2 或者等于 3 的时候,我其实只需要判断一下头尾两个字符是否相等就可以直接下结论

    3.代码

    package part1;
    /**
     * @author haiboWu
     * @create 2020-01-30 19:20
     */
    public class No_05 {
    
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            System.out.println(longestPalindrome("babad"));
        }
    
        public static  String longestPalindrome(String s) {
            int n = s.length();
            if (n < 2) {
                return s;
            }
    
            boolean dp[][] = new boolean[s.length()][s.length()];
            for (int i = 0; i < n; i++) {
                dp[i][i] = true;
            }
            int maxLen = 1;
            int start = 0;
    
            for (int i = 1; i < n; i++) {
                for (int j = 0; j < i; j++) {
                    if (s.charAt(i) == s.charAt(j)) {
                        if (i - j < 3) {
                            dp[j][i] = true;
                        } else {
                            dp[j][i] = dp[j + 1][i - 1];
                        }
                    } else {
                        dp[j][i] = false;
                    }
                    if (dp[j][i]) {
                        int len = i - j + 1;
                        if (len > maxLen) {
                            maxLen = len;
                            start = j;
                        }
                    }
                }
            }
            return s.substring(start, start+maxLen);
        }
    }
    

    方法二:中心扩散法

    遍历每一个索引,以这个索引为中心,利用“回文串”中心对称的特点,往两边扩散,看最多能扩散多远。

    在这里要注意一个细节:回文串在长度为奇数和偶数的时候,“回文中心”的形式是不一样的。

    • 奇数回文串的“中心”是一个具体的字符,例如:回文串 "aba" 的中心是字符 "b";
    • 偶数回文串的“中心”是位于中间的两个字符的“空隙”,例如:回文串串 "abba" 的中心是两个 "b" 中间的那个“空隙”。


      所有的间隙
    package part1;
    
    /**
     * @author haiboWu
     * @create 2020-01-30 19:28
     */
    public class No_05_2 {
        public static void main(String[] args) {
            System.out.println(longestPalindrome("ababd"));
        }
        public static String longestPalindrome(String s){
            int n = s.length();
            if (n < 2) {
                return s;
            }
            int maxLen=1;
            String res=s.substring(0,1);
            for(int i=0;i<n-1;i++){
                String s1=getMaxString(s,i,i);
                String s2=getMaxString(s,i,i+1);
                String maxLenStr=s1.length()>s2.length()?s1:s2;
                if(maxLenStr.length()>maxLen){
                    maxLen=maxLenStr.length();
                    res=maxLenStr;
                }
            }
            return res;
        }
        public static String getMaxString(String s,int left,int right){
            int n=s.length();
    
            while(left>=0&&right<n){
                if(s.charAt(left)==s.charAt(right)){
                    left--;
                    right++;
                }else{
                    break;
                }
            }
            return s.substring(left+1,right);
    
        }
    
    }
    

    3.参考

    上面两种时间复杂度都为O(N),还有第三种时间复杂度为O(N)的方法:Manacher算法

    相关文章

      网友评论

          本文标题:LeetCode_05_最长回文子串

          本文链接:https://www.haomeiwen.com/subject/kdkwthtx.html