131.分割回文串 给你一个字符串 s
,请你将 s
分割成一些子串,使每个子串都是 回文串 。返回 s
所有可能的分割方案。
示例 1:
1 2 输入:s = "aab" 输出:[["a" ,"a" ,"b" ],["aa" ,"b" ]]
示例 2:
Solution
可以根据答案视角的模版来写,如果是回文就添加并且回溯,不是就下一个
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 class Solution { private final List<List<String>> ans = new ArrayList<>(); private final List<String> path = new ArrayList<>(); private String s; public List<List<String>> partition(String s) { this .s = s; dfs(0 ); return ans; } private boolean isPalindrome (int left, int right) { while (left < right) if (s.charAt(left++) != s.charAt(right--)) return false ; return true ; } private void dfs (int i) { if (i == s.length()) { ans.add(new ArrayList<>(path)); return ; } for (int j = i; j < s.length(); ++j) { if (isPalindrome(i, j)) { path.add(s.substring(i, j + 1 )); dfs(j + 1 ); path.remove(path.size() - 1 ); } } } }