Leetcode131 |
您所在的位置：网站首页 › leetcode358 › Leetcode131 |
Leetcode131
|
题目描述
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。 返回 s 所有可能的分割方案。 示例: 输入: "aab" 输出: [ ["aa","b"], ["a","a","b"] ] 解题思路求所有答案，首先排除动态规划，应该是DFS（深度优先搜索） 遇到要求所有组合、可能、排列等解集的题目，一般都是DFS + backtracking（回溯） 回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称 回溯法思考的步骤： 1、画递归树； 2、根据自己画的递归树编码。 1、每一个结点表示剩余没有扫描到的字符串，产生分支是截取了剩余字符串的前缀； 2、产生前缀字符串的时候，判断前缀字符串是否是回文。 如果前缀字符串是回文，则可以产生分支和结点； 如果前缀字符串不是回文，则不产生分支和结点，这一步是剪枝操作。 3、在叶子结点是空字符串的时候结算，此时从根结点到叶子结点的路径，就是结果集里的一个结果，使用深度优先遍历，记录下所有可能的结果。 采用一个tempList 进行路径搜索，在递归执行方法结束以后需要回溯，即将递归之前添加进来的元素拿出去； 总结的解题模板 backTrack(路径， 选择列表) { if (满足结束条件) { result.add(路径); } for (选择 in 选择列表) {// 枚举所有可能的选择 if (!areYouOK(选择)) { 剪枝； continue; } 做选择； backTrack(路径， 选择列表)； 撤销选择，进行回溯； } }优化：可以通过用DP来计算任意s[i:j]是否是回文，并保存结果，再执行DFS，如果发现某条string不是回文，就可以直接退出，从而减少计算量 代码实现 package com.lingluo;/** * @author 灵洛 * @date 23:42 2020/3/14 */ import java.util.ArrayList; import java.util.List; /** * @author 灵洛 * @date 2020/3/14 23:42 * 题目描述：给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。 * 返回 s 所有可能的分割方案。 * 输入: "aab" * 输出:[["aa","b"],["a","a","b"]] * 思路：回溯+动态规划 */ public class Palindrome_partitioning_131 { private int[][] dp; public List partition(String s) { // 记录所有回文结果集 List results = new ArrayList(); if (s == null || s.length() == 0) { return results; } int length = s.length(); // 预处理，dp数组，保存状态 1代表是回文，2代表不是 dp = new int[length][length]; // 字母自己肯定是回文 for (int i = 0; i |
思考如何根据这棵递归树编码：【本文地址】