原题
给定一个字符串 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/
相关推荐
-
leetcode378-有序矩阵中第K小的元素
原题 给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。请注意，它是排序后的第k小元素，而不是第k个元素。 示例: matrix = [ &nbs...
-
leetcode707-设计链表
原题 设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用...
-
leetcode300-最长上升子序列
原题 给定一个无序的整数数组，找到其中最长上升子序列的长度。 示例： 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,10...
-
leetcode706-设计哈希映射
原题 不使用任何内建的哈希表库设计一个哈希映射 具体地说，你的设计应该包含以下的功能 put(key, value)：向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在，更...
-
leetcode116-填充每个节点的下一个右侧节点指针
原题 给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下： struct Node { int val; &...
-
leetcode1028-从先序遍历还原二叉树
原题 我们从二叉树的根节点 root 开始进行深度优先搜索。 在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。（如果节点的深度为 D，...
-
leetcode25-K个一组翻转链表
原题 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。 k 是一个正整数，它的值小于或等于链表的长度。 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原...
-
leetcode83-删除排序链表中的重复元素
今天打算多刷几道算法题 原题 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。 示例 1: 输入: 1->1->2 输出: 1->2 示例 2: 输入: 1->1->...
-
leetcode217-存在重复元素
原题 给定一个整数数组，判断是否存在重复元素。 如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。 示例1： 输入： [1,2,3...
-
leetcode295-数据流的中位数
原题 中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。 例如， [2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 + 3) / 2 = 2....
