JAVA练习334- 分割回文串
题目概览给你一个字符串s请你将s分割成一些 子串使每个子串都是回文串。返回s所有可能的分割方案。示例 1输入s aab输出[[a,a,b],[aa,b]]示例 2输入s a输出[[a]]提示1 s.length 16s仅由小写英文字母组成来源131. 分割回文串 - 力扣LeetCode解题分析方法回溯令当前子串开始位置为 i结束位置为 j那么j 大于等于字符串的长度时返回j 等于字符串长度-1但 [ i , j ] 不为回文子串返回j 等于字符串长度-1且 [ i , j ] 为回文子串记录该子串并讲所有子串记录为一个答案[ i, j ] 范围的子串不为回文子串时j[ i, j ] 范围的子串为回文子串时用 list 记录该子串遍历下一范围回文子串即 [ j 1, j 1 ]下一范围都遍历完成后回溯 list、 i 和 j然后 j 继续遍历时间复杂度O(nx2^n)空间复杂度O(n²)class Solution { public ListListString partition(String s) { ListListString result new ArrayList(); backTracking(s, 0, 0, result, new ArrayList()); return result; } public void backTracking(String s, int i, int j, ListListString result, ListString list) { if (j s.length()) { return; } if (!isPalindrome(s, i, j)) { backTracking(s, i, j 1, result, list); return; } list.add(s.substring(i, j 1)); if (j s.length() - 1) { result.add(new ArrayList(list)); } int prei i, prej j; i j 1; j i; backTracking(s, i, j, result, list); list.remove(list.size()-1); i prei; j prej; backTracking(s, i, j 1, result, list); } public boolean isPalindrome(String s, int i, int j) { if (j s.length()) { return false; } while(i j) { if (s.charAt(i) ! s.charAt(j--)) { return false; } } return true; } }
)
