剑指 Offer II 086. 分割回文子字符串
https://leetcode.cn/problems/M99OJA/
难度中等29收藏分享切换为英文接收动态反馈
给定一个字符串 s ，请将 s 分割成一些子串，使每个子串都是 回文串 ，返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1：
输入：s = "google" 输出：[["g","o","o","g","l","e"],["g","oo","g","l","e"],["goog","l","e"]]
示例 2：
输入：s = "aab" 输出：[["a","a","b"],["aa","b"]]
示例 3：
输入：s = "a" 输出：[["a"]]
提示：
1 <= s.length <= 16s仅由小写英文字母组成
注意：本题与主站 131 题相同： 力扣
通过次数10,814提交次数14,415
class Solution {
int n;
boolean[][] f;
List<List<String>> ans = new ArrayList<List<String>>();
List<String> temp = new ArrayList<String>();
public String[][] partition(String s) {
n = s.length(); //存储字符串的长度
f = new boolean[n][n];
for(int i=0;i<n;i++) Arrays.fill(f[i],true);
//递归判断是否是回文
for(int i=n-1;i>=0;--i) // i的遍历范围是 n-1 ~ 0
for(int j=i+1;j<n;++j) //j的遍历范围是 n~1
f[i][j] = (s.charAt(i)==s.charAt(j)) && f[i+1][j-1];
dfs(s,0);
int rows = ans.size();
String[][] ans1 = new String[rows][];
for(int i=0;i<rows;i++)
{
int cols = ans.get(i).size();
ans1[i] = new String[cols];
for(int j=0;j<cols;j++)
ans1[i][j] = ans.get(i).get(j);
}
return ans1;
}
void dfs(String s,int i)
{
if(i==n)
{
ans.add(new ArrayList<String>(temp));
return;
}
for(int j=i;j<n;j++)
{
if(f[i][j])
{
temp.add(s.substring(i,j+1));
dfs(s,j+1);
temp.remove(temp.size()-1);
}
}
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/69052.html
