LeetCode 131. 分割回文串

冷不防 2022-11-04 13:30 164阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]

//动态规划bool数组求出下表之间是否组成回文串，dfs求具体的回文串
    class Solution {
        
        List<List<String>> res = new ArrayList<>();
        public List<List<String>> partition(String s) {
        
            int len = s.length();
            boolean[][] dp = new boolean[len][len];
            for(int i = len - 1; i >= 0; i--){
        
                for(int j = i; j < len; j++){
        
                    if(i == j)
                        dp[i][j] = true;
                    else if(i + 1 == j)
                        dp[i][j] = (s.charAt(i) == s.charAt(j));
                    else{
        
                        dp[i][j] = (dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j));
                    }
                }
            }
    
            Deque<String> stack = new ArrayDeque<>();
            dfs(stack,len,0,s,dp);
            return res;
        }
    
        private void dfs(Deque<String> path,
                         int len,
                         int start,
                         String s,
                         boolean[][] dp){
        
            if(start == len){
        
                res.add(new ArrayList<>(path));
                return;
            }
            for(int i = start; i < len; i++){
        
                if(dp[start][i]){
        
                    path.addLast(s.substring(start, i + 1));
                    dfs(path, len, i + 1, s, dp);
                    path.removeLast();
                }
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]: /images/20221023/8999d45619d049da9f394b4b8053a65d.png

发表评论取消回复

表情：

评论列表（有 0 条评论，164人围观）

还没有评论，来说两句吧...

相关阅读

相关 131. 分割回文串

131. 分割回文串给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。回文串是正着读和反着读都一样的字符串。

叁歲伎倆/ 2024年03月30日 12:17/ 0 赞/ 60 阅读

相关 LeetCode-131. 分割回文串

目录题目思路回溯题目来源 [131. 分割回文串][131.] 题目思路切割问题类似组合问题。例如对于字符串abcd

深碍√TFBOYSˉ_/ 2024年03月26日 12:52/ 0 赞/ 54 阅读

相关 131.分割回文串

131.分割回文串题干描述解题思路回溯三部曲 1. 递归函数参数 2. 递归函数终止条件 3. 单层搜索的

╰半橙微兮°/ 2023年10月16日 13:38/ 0 赞/ 8 阅读

相关 leetcode 131. 分割回文串

递归暴力求解将字符串进行分割，如果左边是回文串，则对右边进行分割，递归的出口是这个串被分割到空串 class Solution { public:

系统管理员/ 2023年10月10日 10:03/ 0 赞/ 41 阅读

相关 131. 分割回文串

题目： [131. 分割回文串][131.] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_te

绝地灬酷狼/ 2022年12月07日 04:23/ 0 赞/ 181 阅读

相关 leetcode 131. 分割回文串 js

leetcode 131. 分割回文串给你一个字符串 `s`，请你将 `s` 分割成一些子串，使每个子串都是回文串。返回 `s` 所有可能的分割方案。回文串是

ゞ浴缸里的玫瑰/ 2022年11月12日 08:16/ 0 赞/ 160 阅读

相关 LeetCode131. 分割回文串

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。示例: 输入: “aab” 输出: [ ["

小咪咪/ 2022年11月06日 01:56/ 0 赞/ 125 阅读

相关 LeetCode 131. 分割回文串

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。示例: 输入: "aab" 输出:

刺骨的言语ヽ痛彻心扉/ 2022年11月06日 01:51/ 0 赞/ 223 阅读

相关 LeetCode 131. 分割回文串

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

冷不防/ 2022年11月04日 13:30/ 0 赞/ 165 阅读

相关 leetcode 131 分割回文串

前言题目：[131. 分割回文串][131.] 参考题解：[分割回文串-代码随想录][-] 提交代码先切割再判断方法一：思考了下，这道题目的思路为，

梦里梦外;/ 2022年09月12日 13:51/ 0 赞/ 174 阅读