首页 > 其他分享 >动态规划——leetcode5、最长回文子串

动态规划——leetcode5、最长回文子串

时间:2022-08-27 15:48:50浏览次数:51  
标签:子串 leetcode5 int len true dp 回文

1、题目描述:

2、解题方法:动态规划

  动态规划解题步骤:

    1、确定状态

      • 最后一步:如果s[i,...,j]是回文子串,那么需要满足两个条件

        ① s[i] == s[j];

        ② s[i+1,...,j-1]是回文子串;

      • 子问题:我们要验证s[i+1,...,j-1]是不是回文子串
      • 用dp[i][j]来表示s[i,...,j]是不是回文子串

    2、转移方程

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

    3、初始条件和边界情况

      初始条件:dp[i][i] == true;

      边界条件:在s[i] == s[j]的条件下,j-i<=2或者j-i<3,即说明s[i,...,j]的长度为2或者是3时,不用检查是不是回文串。

      

    4、计算顺序

     以字符串s:babab为例,一列一列的进行填表,先升序填列,再升序填行。

       

3、代码:

public String longestPalindrome(String s) {
        int len = s.length();
        if(len < 2){
            return s;
        }
        int maxLen = 1;
        int start = 0;
        char[] res = s.toCharArray();
        boolean[][] dp = new boolean[len][len];

        for(int i = 0; i < len; i++){
            dp[i][i] = true;
        }
        for(int j = 1; j < len; j++){
            for(int i = 0; i < j; i++){
                if(res[i] == res[j]){
                    if(j - i < 3 || dp[i+1][j-1] == true){
                        dp[i][j] = true;
                    }
                    if( j-i+1 > maxLen && dp[i][j] == true){
                        maxLen = j-i+1;
                        start = i;
                    }
                }
            }
        }
        return s.substring(start,start + maxLen);
    }

 

标签:子串,leetcode5,int,len,true,dp,回文
From: https://www.cnblogs.com/LXXin6973/p/16630659.html

相关文章

  • 最长出现偶数次字符子串
    给定一个字符串求子串,使得子串中每个字符出现偶数次,例如S="baaadadd",满足条件的子串有"aa","adad","aaadad",其中最长的是6,输出6这道题一看会想使用滑动窗口解决,但是......
  • #前端算法救赎系列#LeetCode03.无重复字符的最长子串
    3.无重复字符的最长子串给定一个字符串s,请你找出其中不含有重复字符的最长子串的长度。示例1:输入:s="abcabcbb"输出:3解释:因为无重复字符的最长子串是......
  • 一个字符串回文子串数量最大的排列 证明
    CF1063A一个字符串回文子串数量最大的排列证明Problem-1063A-Codeforces若将一个字符串任意排列,要使其中的回文子串数量最多,按字典序排序是一种方法。首先,在一个......
  • PAM(回文自动机/回文树)
    一个由小写字母构成的字符串\(s\),对于\(s\)的每个位置,求出以该位置结尾的回文子串个数。这个字符串被进行了加密,除了第一个字符,其他字符都需要通过上一个位置的答案来......
  • 动态规划——leetcode55、跳跃游戏
    题目描述: 解题方法:动态规划动态规划解题步骤:确定状态:最后一步:如果能跳到最后一个下标,我们考虑他的最后一步到n-1(最后一个下标),这一步是从i跳过......
  • 无重复字符的最长子串
    题目给定一个字符串s,请你找出其中不含有重复字符的最长子串的长度。示例输入:s="abcabcbb"输出:3解释:因为无重复字符的最长子串是"abc",所以其长度为3。......
  • 76. 最小覆盖子串
    76.最小覆盖子串给你一个字符串s、一个字符串t。返回s中涵盖t所有字符的最小子串。如果s中不存在涵盖t所有字符的子串,则返回空字符串""。 注意:对......
  • 3. 无重复字符的最长子串
    给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度(子串,连续,子序列,可以不连续)。提示:0<=s.length<=5*104s 由英文字母、数字、符号和空格组......
  • 2022牛客多校 补赛 C Cmostp(区间结尾本质不同子串)
    多次询问求一个串的结尾在\([l,r]\)之间的本质不同子串个数。此题是求一个区间的不同元素的问题,使用扫描线的方法解决,即每次加入一个元素就将这个位置\(+1\),这个元素上一......
  • leetcode53-最大子数组和
    最大子数组和dp记录当前位置的累加和以及最大子数组和。遍历数组并累加,如果发现累加和小于0,那么前面累加的东西反而会使得后面的和变小,那么直接丢弃,将累加和清零。cl......