https://leetcode.cn/problems/palindrome-partitioning/
给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
输入:s = "aab"
输出:[["a","a","b"],["aa","b"]]
1 <= s.length <= 16
s 仅由小写英文字母组成
回溯法,采用截取字符串来判断回文。
时间复杂度 O(n2) 空间复杂度 O(n)
Java
LinkedList<String> path = new LinkedList<>(); List<List<String>> ans = new ArrayList<>(); public List<List<String>> partition(String s) { trace(s, 0); return ans; } public void trace(String s, int index) { if (index >= s.length()) { ans.add(new ArrayList<>(path)); return; } for (int i = index + 1; i <= s.length(); i++) { String tmp = s.substring(index, i); if (is(tmp)) { path.add(tmp); trace(s, i); path.removeLast(); } } } public boolean is(String s) { for (int i = 0, j = s.length() - 1; i < j; i++, j--) { if (s.charAt(i) != s.charAt(j)) { return false; } } return true; }