Palindrome Partitioning
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
Example:
Given s = "aab", return:
[
["aa","b"],
["a","a","b"]
]
Solution:
Similar to Subsets problem. We could use depth first search to solve it.
Code:
public class Solution {
public List<List<String>> partition(String s) {
List<List<String>> res = new ArrayList<>();
if (s == null || s.length() == 0) {
return res;
}
List<String> path = new ArrayList<>();
char[] chars = s.toCharArray();
partitionHelper(chars, 0, path, res);
return res;
}
private void partitionHelper(char[] chars, int index, List<String> path,
List<List<String>> res) {
if (index >= chars.length) {
res.add(new ArrayList<>(path));
}
StringBuilder sb = new StringBuilder();
for (int i = index; i < chars.length; i++) {
sb.append(chars[i]);
if (isPalindrome(chars, index, i)) {
path.add(sb.toString());
partitionHelper(chars, i + 1, path, res);
path.remove(path.size() - 1);
}
}
}
private boolean isPalindrome(char[] chars, int start, int end) {
while (start < end) {
if (chars[start] != chars[end]) {
return false;
}
start++;
end--;
}
return true;
}
}