Palindrome Partitioning
LintCode-136.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"]
]
public class Solution {
/**
* @param s: A string
* @return: A list of lists of string
*/
public List<List<String>> partition(String s) {
List<List<String>> result = new ArrayList<>();
if (s == null || s.length() == 0) {
return result;
}
partitionHelper(s, result, new ArrayList<String>(), 0);
return result;
}
void partitionHelper(String s, List<List<String>> result, List<String> list, int start) {
if (start == s.length()) {
result.add(new ArrayList<String>(list));
return;
}
for (int i = start; i < s.length(); i++) {
String subStr = s.substring(start, i + 1);
if (isPalindrome(subStr)) {
list.add(subStr);
partitionHelper(s, result, list, i + 1);
list.remove(list.size() - 1);
}
}
}
boolean isPalindrome(String s) {
int start = 0, end = s.length() - 1;
while (start < end) {
if (s.charAt(start) == s.charAt(end)) {
start++;
end--;
} else {
return false;
}
}
return true;
}
}
Hope this helps,
Michael