LeetCode 131. 分割回文串

冷不防 2022-11-04 13:30 126阅读 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