Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
Example:
Input: "aab" Output: [ ["aa","b"], ["a","a","b"] ]
分析¶
比较规矩的回溯法的问题。注意细节即可。
private List<List<String>> res; public List<List<String>> partition(String s) { res = new ArrayList<>(); partitionHelper(new ArrayList<>(), s); return res; } private void partitionHelper(ArrayList<String> list, String s) { if (s.length() == 0) {res.add(list); return; } int i = 1, n = s.length(); while (i <= n) { String sub = s.substring(0, i); if (!isValidPalindrome(sub)) {i++; continue;} list.add(sub); partitionHelper((ArrayList<String>) list.clone(), s.substring(i, n)); list.remove(list.size() - 1); i++; } } private boolean isValidPalindrome(String s) { if (s == null) return false; int left = 0, right = s.length() - 1; while (left <= right) if (s.charAt(left++) != s.charAt(right--)) return false; return true; }
近期评论