Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = “aab”,
Return
1 2 3 4
| [ ["aa","b"], ["a","a","b"] ]
|
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
| public class Solution { public List<List<String>> partition(String s) { List<List<String>> result = new ArrayList<>(); partitionString(result, new ArrayList<String>(), s, 0); return result; } public void partitionString(List<List<String>> result, ArrayList<String> cur, String s, int start) { if (start == s.length()) { result.add(new ArrayList<String>(cur)); } else { for (int i = start; i < s.length(); i++) { if (isPalindrome(s, start ,i)) { cur.add(s.substring(start, i + 1)); partitionString(result, cur, s, i + 1); cur.remove(cur.size() - 1); } } } } public boolean isPalindrome(String s, int start, int end) { while (start < end) { if (s.charAt(start++) != s.charAt(end--)) return false; } return true; } }
|