Problem¶
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
Example 1:
Example 2:
Constraints:
1 <= s.length <= 16scontains only lowercase English letters.
Solve¶
Preprocess data¶
The problem will be easier when we know all the palindrome substring of s. This is quite easy, we focusing this pattern of a palindrome string
where c is repeating character.
There is a lot of way to implement this function, the final result will be a func(x,y) that can quickly check substring s[x:y] is a palindrome or not in O(1) lookup time
Dynamic programming¶
palindrome_string = []
def isPalindrome(x, y):
return palindrome_string[y - x][x]
# Find all palindrome
for size in range(0, len(s)):
curr_palindrome_string = []
for i in range(0, len(s)-size):
if size == 0:
curr_palindrome_string.append(True)
continue
if size == 1:
curr_palindrome_string.append(s[i] == s[i+size])
continue
check = s[i] == s[i+size]
check &= isPalindrome(i+1, i+size-1)
curr_palindrome_string.append(check)
palindrome_string.append(curr_palindrome_string)
We have isPalindrome is the func(x,y)
Recursion¶
cache2 = {}
def isPalindrome(x,y):
if x > y:
return False
if x == y:
return True
if (x,y) in cache2:
return cache2[(x,y)]
if s[x] != s[y]:
cache2[(x, y)] = False
return False
if s[x+1:y] != "" and not isPalindrome(x+1,y-1):
cache2[(x, y)] = False
return False
cache2[(x, y)] = True
return True
Getting all the palindrome split¶
After preprocessing data, We can then try to split the string base on:
- If the substring is palindrome, then try split it, continue split the remaining substring.
- If the substring isn’t palindrome, pass
class Solution:
def partition(self, s: str) -> List[List[str]]:
def isPalindrome(x, y):
# Last implementation
cache = {}
def palindrome_split(x, y):
if x >= y:
return [[|]]
if x == y - 1:
return [[s[x:y|s[x:y]]]
if (x, y) in cache:
return cache[(x,y)]
possible = []
for end in range(x,y):
start = x
curr = s[start:end+1]
res = []
if isPalindrome(start, end):
all_pali = palindrome_split(end+1, y)
for pali in all_pali:
res.append([curr] + pali)
possible += res
cache[(x,y)] = possible
return cache[(x,y)]
return palindrome_split(0, len(s))
Java implementation¶
class Solution {
private int[][] cacheIsPalindrome;
private int n;
private List<List<String>>[][] cachePalindromeSplit;
private String s;
private boolean isPalindrome(int x, int y) {
if (x > y) return false;
if (x == y) return true;
if (cacheIsPalindrome[x][y] != 0) return cacheIsPalindrome[x][y] > 0;
if (s.charAt(x) != s.charAt(y)) {
cacheIsPalindrome[x][y] = -1;
return false;
}
if ((x + 1 < y) && !isPalindrome(x + 1, y - 1)) {
cacheIsPalindrome[x][y] = -1;
return false;
}
cacheIsPalindrome[x][y] = 1;
return true;
}
private List<List<String>> palindromeSplit(int x, int y) {
if (x >= y) {
List<List<String>> result = new ArrayList<>();
result.add(new ArrayList<>());
return result;
}
if (x == y - 1) {
List<List<String>> result = new ArrayList<>();
List<String> single = new ArrayList<>();
single.add(s.substring(x, y));
result.add(single);
return result;
}
if (!cachePalindromeSplit[x][y].isEmpty()) {
return cachePalindromeSplit[x][y];
}
List<List<String>> possible = new ArrayList<>();
for (int end = x; end < y; end++) {
int start = x;
String curr = s.substring(start, end + 1);
List<List<String>> res = new ArrayList<>();
if (isPalindrome(start, end)) {
List<List<String>> all_pali = palindromeSplit(end + 1, y);
for (List<String> pali : all_pali) {
List<String> combined = new ArrayList<>();
combined.add(curr);
combined.addAll(pali);
res.add(combined);
}
}
possible.addAll(res);
}
cachePalindromeSplit[x][y] = possible;
return possible;
}
public List<List<String>> partition(String s) {
n = s.length();
cacheIsPalindrome = new int[n+1][n+1];
cachePalindromeSplit = new ArrayList[n+1][n+1];
this.s = s;
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
cachePalindromeSplit[i][j] = new ArrayList<>();
return palindromeSplit(0, n);
}
}
Comparison¶
- Caching can make a different
- Generate data on the fly using recursion may help on overall python time cost
| Time Submitted | Status | Runtime | Memory | Language |
|---|---|---|---|---|
| 08/11/2023 19:44 | Accepted | 502 ms | 33.2 MB | python3 |
| 08/11/2023 19:05 | Accepted | 521 ms | 32.1 MB | python3 |
| 08/11/2023 19:02 | Accepted | 600 ms | 32.3 MB | python3 |
- The caching is replace by allocate a two dimension array, here is the different between caching and not
| Time Submitted | Status | Runtime | Memory | Language |
|---|---|---|---|---|
| 08/11/2023 22:05 | Accepted | 46 ms | 56 MB | java |
| 08/11/2023 22:00 | Accepted | 7 ms | 55.2 MB | java |
- If you want to make it even faster, we can do some cleaver way utilizing bottom-up call to build up each
List<String>. Also, theyvariable inpalindromeSplitcan be remove, it’s not changing after all of calculations. The result implementation look like this:
private List<List<String>> ans;
private void FindSubstringsq`1(int ind, ArrayList<String> list) {
if (ind == n) {
ans.add(new ArrayList<String>(list));
return;
}
for (int i = ind + 1; i <= n; i++) {
if (!isPalindrome(ind, i-1)) continue;
list.add(s.substring(ind, i));
FindSubstrings(i, list);
list.remove(list.size() - 1);
}
}
public List<List<String>> partition(String s) {
n = s.length();
this.s = s;
ans = new ArrayList<List<String>>();
FindSubstrings(0, new ArrayList<String>());
return ans;
}
Last update :
August 18, 2023
Created : August 16, 2023
Created : August 16, 2023