原题
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例:
输入: "aab" 输出: [ ["aa","b"], ["a","a","b"] ]
解法
思想
在字符串中搜索是回文串的子字符串，可以使用dfs。
但判断子字符串是不是回文串的时候，可以下功夫优化，这里不能使用我在leetcode125-验证回文串中用到的方法，因为子字符串之间存在很多个重复的单元。
那么就可以使用动态规划的方法判断子字符串是否为回文串：使用一个二维的dp数组，dp[i][j]代表在字符串中下标i起始，下标j截止的子字符串是否为回文串，根据回文串的判断方法，可以得到状态转移方程dp[i][j] = s.charAt(i)==s.charAt(j) && dp[i+1][j-1]。
代码
class Solution {
boolean[][] dp;
char[] chars;
List<List<String>> ans = new ArrayList<>();
public List<List<String>> partition(String s) {
int length = s.length();
chars = s.toCharArray();
dp = new boolean[length][length];
List<String> list = new ArrayList<>();
dfs(0,list);
return ans;
}
// 子字符串是否是回文串，使用动态规划判断
public boolean isPalindrome(int startIndex,int endIndex){
if(startIndex >= endIndex) return true;
boolean result = chars[startIndex] == chars[endIndex] && isPalindrome(startIndex+1,endIndex-1);
dp[startIndex][endIndex] = result;
return result;
}
// 从下标为startIndex处进行dfs搜索
public void dfs(int startIndex,List<String> list){
for(int i = startIndex;i<chars.length;i++){
if(isPalindrome(startIndex,i)){
List<String> copy = new ArrayList<>(list);
copy.add(new String(chars,startIndex,i-startIndex+1));
if(i == chars.length-1) ans.add(copy);
else dfs(i+1,copy);
}
}
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode131-%e5%88%86%e5%89%b2%e5%9b%9e%e6%96%87%e4%b8%b2/
相关推荐
-
leetcode1160-拼写单词
原题 给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。 假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字...
-
leetcode542-01矩阵
原题 给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。 两个相邻元素间的距离为 1 。 示例1: 输入: 0 0 0 0 1 0 0 0 0 输出: 0 0 ...
-
leetcode543-二叉树的直径
原题 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。 示例: 给定二叉树 1 / \ 2 3 / \ 4 5...
-
leetcode287-寻找重复数
原题 给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。 ...
-
leetcode142-环形链表II
原题 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始...
-
leetcode2-两数相加
原题 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。 如果，我们将这两个数相加起来，则会返回...
-
leetcode77-组合
原题 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。 示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [...
-
leetcode443-压缩字符串
原题 给定一组字符，使用原地算法将其压缩。 压缩后的长度必须始终小于或等于原数组长度。 数组的每个元素应该是长度为1 的字符（不是 int 整数类型）。 在完成原地修改输入数组后，...
-
leetcode1103-分糖果II
原题 排排坐，分糖果。 我们买了一些糖果 candies，打算把它们分给排好队的 n = num_people 个小朋友。 给第一个小朋友 1 颗糖果，第二个小朋友 2 颗，依此类...
-
leetcode67-二进制求和
原题 给定两个二进制字符串，返回他们的和（用二进制表示）。 输入为非空字符串且只包含数字 1 和 0。 示例 1: 输入: a = “11”, b = “1” 输出: “100” ...
