131. Palindrome Partitioning (Medium)
https://leetcode.com/problems/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:
Input: "aab" Output: [ ["aa","b"], ["a","a","b"] ]
Solutions
class Solution {
// key is the substring, value is whether it is palindrome or not.
Map<String, Boolean> validPalindromes = new HashMap<>();
// strings or substrings of them can not form the palindrome
Map<String, Boolean> unpartitionableStrs = new HashMap<>();
Map<String, List<List<String>>> solutions = new HashMap<>();
public List<List<String>> partition(String s) {
if (s == null || s.isEmpty()) {
return null;
}
// Sort out all the possible substrings that satisfy all criterion of palindrome string.
sortOutPalindrome(s);
recurse(s);
return solutions.get(s);
}
private void sortOutPalindrome(String s) {
// i is the length of palindrome
for (int i = 1; i <= s.length(); i++) {
// j is the start index of the palindrome
for (int j = 0; j < s.length() - i + 1; j++) {
String str = s.substring(j, j + i);
// every single char is a valid palindrome
if (i == 1) {
validPalindromes.put(str, true);
continue;
}
// find out all the palindrome of length 2
if (i == 2) {
if (str.charAt(0) == str.charAt(1)) {
validPalindromes.put(str, true);
} else {
validPalindromes.put(str, false);
}
continue;
}
// for length >= 3
if (!validPalindromes.get(str.substring(1, i - 1))) {
validPalindromes.put(str, false);
continue;
}
// check out if both side is equal
if (s.charAt(j) == s.charAt(j + i - 1)) {
validPalindromes.put(str, true);
}
// not equal and unable to form the palindrome
else {
validPalindromes.put(str, false);
}
}
}
}
private List<List<String>> recurse(String substr) {
List<List<String>> results = new ArrayList<>();
// partitionable, return solution of length 0.
if (substr == null || substr.isEmpty()) {
return results;
}
// unpartitionable, return null.
if (unpartitionableStrs.containsKey(substr)) {
return null;
}
// if already permeated, return the answer
if (solutions.containsKey(substr)) {
return solutions.get(substr);
}
for (int i = 0; i < substr.length(); i++) {
String str = substr.substring(0, i + 1);
// not a valid palindrome, no necessity to dig deep
if (!validPalindromes.get(str)) {
continue;
}
// tmp is the container to hold possible palindrome arrangements for substr[i+1:].
List<List<String>> tmp = recurse(substr.substring(i + 1));
// unpartitionable
if (tmp == null) {
continue;
}
// Problem occurs if we modify it directly owing to the fact that tmp is possessed substr[i+1:].
// As a consequence, we are expected to instantiate a brand new List to union str and the results in tmp.
tmp = union(tmp, str);
results.addAll(tmp);
}
// no possible partition scheme for string s
if (results.isEmpty()) {
unpartitionableStrs.put(substr, false);
return null;
}
solutions.put(substr, results);
return results;
}
private List<List<String>> union(List<List<String>> results, String str) {
List<List<String>> ans = new ArrayList<>();
// results is empty which means it just hit the end of string.
if (results.isEmpty()) {
List<String> tmp = new ArrayList<>();
tmp.add(str);
ans.add(tmp);
return ans;
}
for (List<String> sol : results) {
// create new container to keep values
List<String> tmp = new ArrayList<>(sol);
tmp.add(0, str);
ans.add(tmp);
}
return ans;
}
}