精华内容
下载资源
问答
  • leetcode-回文串

    2021-03-08 20:15:12
    分割回文串 II 给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是回文。 返回符合要求的 最少分割次数 。 示例 1: 输入:s = “aab” 输出:1 解释:只需一次分割就可将 s 分割成 [“aa”,“b”] 这样两...
    1. 分割回文串 II
      给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是回文。

    返回符合要求的 最少分割次数 。

    示例 1:

    输入:s = “aab”
    输出:1
    解释:只需一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子串。
    示例 2:

    输入:s = “a”
    输出:0
    示例 3:

    输入:s = “ab”
    输出:1

    提示:

    1 <= s.length <= 2000
    s 仅由小写英文字母组成

    思路:

    1. 根据回文串的状态转移方程得到所有子串是否是回文串;
    2. 利用dp记录遍历最小分割次数;
    class Solution {
    public:
        int minCut(string s) {
            n = s.size();
            if (n == 1) {
                return 0;
            }
            vector<vector<bool>> f(n, vector<bool>(n, true)); // 记录所有子串是否是回文串
            for (int i = n - 1; i >= 0; i--) {
                for (int j = i + 1; j < n; j++) {
                    f[i][j] = (s[i] == s[j] && f[i + 1][j - 1]); // i + 1不会越界
                }
            }
    
            vector<int> dp(n, INT_MAX); // 记录最小分割次数
            dp[0] = 0;
            for (int i = 1; i < n; i++) {
                if (f[0][i]) {
                    dp[i] = 0;
                    continue;
                }
                dp[i] = dp[i - 1] + 1;
                for (int j = 0; j < i; j++) {
                    if (f[j][i]) {
                        dp[i] = min(dp[j - 1] + 1, dp[i]); // 跑到这里表示f[0][i]不是回文串,所以dp[j - 1]不会越界
                    }
                }
            }
    
            return dp[n - 1];
        }
    
    private:
        int n;
    };
    
    展开全文
  • Leetcode回文串分割IV

    2021-02-01 11:39:42
    题目: 给你一个字符s,如果可以将它分割成三个非空回文子字符,那么返回true,否则返回false。 当一个字符正着读和反着读是...解释:s 没办法被分割3 个回文子字符。 提示: 3 <= s.length &l...

    题目:

    给你一个字符串 s ,如果可以将它分割成三个 非空 回文子字符串,那么返回 true ,否则返回 false 。

    当一个字符串正着读和反着读是一模一样的,就称其为 回文字符串 。

    示例 1:

    输入:s = "abcbdd"
    输出:true
    解释:"abcbdd" = "a" + "bcb" + "dd",三个子字符串都是回文的。
    示例 2:

    输入:s = "bcbddxy"
    输出:false
    解释:s 没办法被分割成 3 个回文子字符串。

    提示:

    3 <= s.length <= 2000
    s​​​​​​ 只包含小写英文字母。

    代码:

    class Solution {
    public:
        bool checkPartitioning(string s) {
            int len=s.length();
        if(len<3)return false;
        vector<vector<int>> v(len,vector<int>(len,0));
        for(int i=1;i<=len;i++){
            for(int l=0;l<len-i+1;l++){
                int r=l+i-1;
                if(s[l]==s[r]){
                    if(r-l<=1)v[l][r]=r-l+1;
                    else{
                        v[l][r]=v[l+1][r-1]==0?0:2+v[l+1][r-1];
                    }
                }else{
                    v[l][r]=0;
                }
            }
        }
        for(int i=1;i<len-1;i++){
            for(int j=i+1;j<len;j++){
                if(v[0][i-1]!=0&&v[i][j-1]!=0&&v[j][len-1]!=0)return true;
            }
        }
        return false;
        }
    };

    想法:使用二维数组d表示该回文串,当d[i][j]==0时表示,index i和index j之间的子串不构成回文串,当d[i][j]!=0时,表示index i和index j之间的子串构成回文串。建立好数组以后,使用i和j表示三个非空回文串之间的分割点,遍历i,j,如果有满足情况的,那么返回true;否则,返回false。

    展开全文
  • 题目miaos 给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是回文。...一重动态规划求解的是回文串,判断每个子串是否是回文串, 当i>j 时,空串也是回文串,其次当i<=j 时, 当s[i]==s[j] 且 f[i+1

    题目miaos
    给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是回文。返回符合要求的 最少分割次数 。

    示例 1:
    输入:s = “aab”
    输出:1
    解释:只需一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子串。
    示例 2:
    输入:s = “a”
    输出:0
    示例 3:
    输入:s = “ab”
    输出:1

    二重动态规划:
    一重动态规划求解的是回文串,判断每个子串是否是回文串,

    • 当i>j 时,空串也是回文串,其次当i<=j 时,
    • 当s[i]==s[j] 且 f[i+1][j-1] =true 时 f[i][j] =true ,边界情况,子串长度小于等于2。

    第二重动态规划是去寻找最小的分割次数。

    • 状态表示:f[i] 表示把前i个字符串分割成回文串需要的最少分割次数。
    • 状态计算:枚举回文串的起点i ,枚举最后一段回文串的起点 i,然后利用 st[i][j] 可知 s[i…j]是否是回文串,如果是回文串,则 f[j] 可以从 f[i−1]+1转移
    class Solution {
    public:
        int minCut(string s) {
            int n = s.size();
            vector<int> f(n,INT_MAX);
            vector<vector<bool>> g(n,vector<bool>(n));
            for(int j=0;j<n;j++)
            {
                for(int i=0;i<=j;i++)
                {
                    if(i==j) g[i][j]=true;
                    if(s[i]==s[j] && (j-i<=2 || g[i+1][j-1])) g[i][j]=true;
                }
            }
            for(int j=0;j<n;j++)
            {
                if(g[0][j]) f[j]=0;
                else 
                {
                    for(int i=0;i<j;i++)
                    {
                        if(g[i+1][j]) f[j]=min(f[j],f[i]+1);
                    }
                }            
            }
            return f[n-1];
        }
    };
    
    展开全文
  • Leetcode- 分割回文串 II

    2021-01-10 20:05:15
    目录 1.题目描述 2. 解题思路 2.1 动态规划 3.源代码 1.题目描述 ... 分割回文串 可以先去做下因为要切割出多个回文串,那么意味着就我们需要判断哪个子串是回文串, 如果我们不做预处理,那...

    目录

    1.题目描述

    2. 解题思路

    2.1 动态规划

    3.源代码


    1.题目描述

    给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。

    返回符合要求的最少分割次数。

    示例:

    输入: "aab"
    输出: 1
    解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

    2. 解题思路

    2.1 动态规划

    没做过 5.最长回文串 和 131. 分割回文串 可以先去做下因为要切割出多个回文串,那么意味着就我们需要判断哪个子串是回文串,
    如果我们不做预处理,那么就需要每次遍历字符串的时候调用 isPalindrome(s, i, j) 方法判断是否回文
    这样一个子串如果被多次访问,那么就需要多次遍历,这显然效率低下
    因此,我们需要对整个字符串进行一次预处理,找出所有回文串的位置,比如 can[i][j] == true 表示 [i, j] 子串是回文串
    这样我们后续只需要判断 can[i][j] 就可以直接得知是否是子串了
    比如字符串 "aab"
    can[0][0] = can[0][1] = can[1][1] = can[2][2] = true

    预处理完成了,其实就是很简单的 dp 了
    dp[i] 表示 [0, i] 分割为回文串所需要的最少切割数(对 dp 稍微熟悉的应该知道怎么做了)
    步骤 1:思考状态
    状态就尝试定义成题目问的那样,看看状态转移方程是否容易得到。

    dp[i]:表示前缀子串 s[0:i] 分割成若干个回文子串所需要最小分割次数。

    步骤 2:思考状态转移方程
    思考的方向是:大问题的最优解怎么由小问题的最优解得到。

    即 dp[i] 如何与 dp[i - 1]、dp[i - 2]、...、dp[0] 建立联系。

    比较容易想到的是:如果 s[0:i] 本身就是一个回文串,那么不用分割,即 dp[i] = 0 ,这是首先可以判断的,否则就需要去遍历;

    接下来枚举可能分割的位置:即如果 s[0:i] 本身不是一个回文串,就尝试分割,枚举分割的边界 j。

    如果 s[j + 1, i] 不是回文串,尝试下一个分割边界。

    如果 s[j + 1, i] 是回文串,则 dp[i] 就是在 dp[j] 的基础上多一个分割。

    于是枚举 j 所有可能的位置,取所有 dp[j] 中最小的再加 1 ,就是 dp[i]。

    得到状态转移方程如下:

    dp[i] = min([dp[j] + 1 for j in range(i) if s[j + 1, i] 是回文])

    步骤 3:思考初始状态
    初始状态:单个字符一定是回文串,因此 dp[0] = 0。

    步骤 4:思考输出
    状态转移方程可以得到,并且状态就是题目问的,因此返回最后一个状态即可,即 dp[len - 1]。

    步骤 5:思考是否可以优化空间
    每一个状态值都与之前的状态值有关,因此不能优化空间。

    3.源代码

     

    class Solution {
       boolean[][] can;
        public int minCut(String s) {
            int len = s.length();
            can = new boolean[len][len];
            for(int i = 0; i < len; i++){
                prePro(can, s, i, i, len);
                prePro(can, s, i, i + 1, len);
            }
            /*
    
            */  
            int[] dp = new int[len + 1];
            Arrays.fill(dp, len);
            dp[0] = 0;
            for(int i = 0; i < len; i++){
                for(int j = 0; j <= i; j++){
                    if(can[j][i]){
                        dp[i + 1] = Math.min(dp[j] + 1, dp[i + 1]);
                    }
                }
            }
            return dp[len] - 1;
        }
           /*
                预处理,先找到所有能够形成回文串的位置
                中心扩展,最坏情况下整个字符串都是回文,那么是 O(n^2)
            */
        private void prePro(boolean[][] dp, String str, int left, int right, int len){
    
            while(left >= 0 && right < len && str.charAt(left) == str.charAt(right)){
                dp[left][right] = true;
                left--;
                right++;
            }
        }
    
    
    }

    Leetcode 提交截图:

     

    展开全文
  • Leetcode-分割回文串

    2021-01-09 21:31:15
    给定一个字符串s,将s分割成一些子串,使每个子串都是回文串。 返回s所有可能的分割方案。 示例1: 输入: "aab" 输出: 1 解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。 2.解题思路 本题这...
  • 给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。 返回符合要求的最少分割次数。 示例: 输入:"aab"输出: 1解释: 进行一次分割就可将s 分割成 ["aa","b"] 这样两个回文子串。 使用dfs完败,字符...
  • 给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。 回文串 是正着读和反着读都一样的字符串。 示例 1: 输入:s = “aab” 输出:[[“a”,“a”,“b”],[“aa”,“b...
  • 给你一个字符 s,请你将 s 分割成一些子串,使每个子串都是回文。 返回符合要求的 最少分割次数 。 示例 1: 输入:s = “aab” 输出:1 解释:只需一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子串。 ...
  • 求最小的分割次数,既然是分割回文串II必然和分割回文串I有相通之处,还记得昨天的采用动态规划嘛,所以可以求解f(i)最小分割次数,f(i)为s[0…i]之间的最小分割次数,求解f(i)考虑枚举出s[0…i]分割出的最后一个...
  • 分割回文串Golang版 1. 问题描述 给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。 回文串 是正着读和反着读都一样的字符串。 2. 思路 回溯法模板题 3. 代码 ...
  • 131. 分割回文串 给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。 返回 s 所有可能的分割方案。 示例: 输入: “aab” 输出: [ [“aa”,“b”], [“a”,“a”,“b”] ] 本题使用回溯算法: 1.首先...
  • 分割回文串 自己学习回顾所用,这是官方给的答案 题目:aab 1、搜索+回溯法枚举出所有可能的回文子串,假设在s[0…i]已经判断出所有的回文子串,分割的答案放已经放入数组ans中,所以需要枚举出下一个回文串的右边界...
  • 分割回文串 II 给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是回文。 返回符合要求的 最少分割次数 。 示例 1: 输入:s = “aab” 输出:1 解释:只需一次分割就可将 s 分割成 [“aa”,“b”] 这样两...
  • 分割回文串II 题干 给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是回文。 返回符合要求的 最少分割次数 。 示例 1: 输入:s = “aab” 输出:1 解释:只需一次分割就可将 s 分割成 [“aa”,“b”...
  • 分割回文串 给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。 返回符合要求的最少分割次数。 示例: 输入:"aab" 输出: 1 解释: 进行一次分割就可将s 分割成 ["aa","b"] 这样两个回文子串。...
  • 131. 分割回文串 给定一个字符串s,将s分割成一些子串,使每个子串都是回文串。 返回s所有可能的分割方案。 示例: 输入:"aab" 输出: [ ["aa","b"], ["a","a&...
  • leetcode131. 分割回文串

    2020-08-19 10:37:01
    题目: 给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。返回 s 所有可能的分割方案。 输入: "aab" 输出: [ ["aa","b"] ["a","a","b"] ] 回溯 DFS递归树: 1、每一个结点表示剩余没有扫描到的字符串...
  • 分割回文串,题意如下: 给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。 回文串 是正着读和反着读都一样的字符串。 首先要仔细读题,题目要求是将s分割成子串...
  • leetcode131_分割回文串

    2020-03-17 13:17:53
    给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。返回 s 所有可能的分割方案。 示例: 输入: “aab” 输出: [ [“aa”,“b”], [“a”,“a”,“b”] ] 由于要求给出具体路径,这里考虑回溯法 这种题目...
  • dp[i][j]表示第i个字符到第j个字符分割回文串的最少次数。 枚举分割值k即可。dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+1) 复杂度 n^3。过不了最后一组数据。采用面向数据编程的方法,可以通过。 class ...
  • 本篇推文共计2000个字,阅读时间约3分钟。01题目描述题目描述:给你一个字符s,请你将s分割成一些子串,使每个子串都是回文。返回符合要求的最少分割次数。示例:输入:s = "a...
  • 本篇推文共计2000个字,阅读时间约3分钟。01题目描述题目描述:给定一个字符串s,将s分割成一些子串,使每个子串都是回文串。返回s所有可能的分割方案。示例:输入:"aab"...
  • 131.分割回文串 给定一个字符串s,将s分割成一些子串,使每个子串都是回文串。 返回s所有可能的分割方案。 示例: 输入:"aab" 输出: [ ["aa","b"], ["a","a","b"] ] 解题思路:回溯法。回溯法的思路是使用...
  • 给你一个字符串s,请你将s分割成一些子串,使每个子串都是回文串。返回s所有可能的分割方案。 回文串是正着读和反着读都一样的字符串。 代码: 思路分析:其实分割字符串 和 组合 问题是类似的 1、递归结束...
  • 做这个题之前,可以先看一下分割回文串,理解了后,其实简单的解法就是分割出所有的回文串,然后找分割后最少的那一种即可。但是这样的话,因为遍历所有回文串的时间复杂度是o(n3)o(n^3)o(n3),所以会超时。 借鉴...
  • LeetCode#131.分割回文串

    2019-11-25 12:25:14
    分割回文串:给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。 返回 s 所有可能的分割方案。 分析:首先要用动态规划来标记出回文子串的位置,dp[i][j]=true表示字串i到j是回文。因此动态规划判断...
  • 分割回文串 II,是昨天那道题的进阶版,题意如下: 给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是回文。 返回符合要求的 最少分割次数 。 1 <= s.length <= 2000 首先看到这个题的数据范围是...
  • 给你一个字符串 s,请你将 s 分割成一些子串,使每...先利用动态规划对字符串进行预处理,找出回文串中所有的回文子串。然后继续利用动态规划方法,用int [ ]min 记录字符串前i个字符的最少分割次数(i=0,1,2,3…min

空空如也

空空如也

1 2 3 4 5
收藏数 99
精华内容 39
关键字:

leetcode分割回文串3