四刷 07/2022
Version #1 Bottom-up DFS with memorization
Time - There are O(2^N) possible partitions and for each partition we use O(N) to get the substring
So total time complexity is O(N*2^N)
Space O(N^2)
Runtime: 21 ms, faster than 46.18% of Java online submissions for Palindrome Partitioning.
Memory Usage: 183.8 MB, less than 65.31% of Java online submissions for Palindrome Partitioning.
class Solution {
public List<List<String>> partition(String s) {
int len = s.length();
boolean[][] isPalin = new boolean[len][len];
for (int j = 0; j < len; j++) {
for (int i = j; i >= 0; i--) {
if (i == j) {
isPalin[i][j] = true;
} else if (i + 1 == j) {
isPalin[i][j] = s.charAt(i) == s.charAt(j);
} else {
isPalin[i][j] = s.charAt(i) == s.charAt(j) && isPalin[i + 1][j - 1];
}
}
}
return helper(s, 0, new HashMap<>(), isPalin);
}
// result of palindrome partitioning of substring index
private List<List<String>> helper(String s, int startIndex, Map<Integer, List<List<String>>> mem, boolean[][] isPalin) {
if (mem.containsKey(startIndex)) {
return mem.get(startIndex);
}
List<List<String>> result = new ArrayList<>();
if (startIndex == s.length()) {
result.add(new ArrayList<>(Arrays.asList(new String[]{})));
return result;
}
for (int endIndex = startIndex; endIndex < s.length(); endIndex++) {
if (!isPalin[startIndex][endIndex]) {
continue;
}
String curr = s.substring(startIndex, endIndex + 1);
List<List<String>> nextResult = helper(s, endIndex + 1, mem, isPalin);
for (List<String> next : nextResult) {
List<String> subResult = new ArrayList<>();
subResult.add(curr);
subResult.addAll(next);
result.add(subResult);
}
}
mem.put(startIndex, result);
return result;
}
}
三刷 06/2022
Version #2 Top-bottom DFS with memorization
class Solution {
public List<List<String>> partition(String s) {
List<List<String>> result = new ArrayList<>();
dfs(s, 0, new ArrayList<>(), result, new Boolean[s.length() + 1][s.length() + 1]);
return result;
}
private void dfs(String s, int index, List<String> path, List<List<String>> result, Boolean[][] dp) {
// System.out.printf("index %d\n", index);
if (index == s.length()) {
result.add(new ArrayList<>(path));
return;
}
for (int i = s.length() - 1; i >= index; i--) {
String substr = s.substring(index, i + 1);
if (!isPalin(s, index, i, dp)) {
continue;
}
path.add(substr);
// System.out.printf("substr %s added\n", substr);
dfs(s, i + 1, path, result, dp);
path.remove(path.size() - 1);
}
}
// Returns if substring [start, end] is palindrome
private boolean isPalin(String s, int start, int end, Boolean[][] dp) {
if (start >= end) {
return true;
}
if (dp[start][end] != null) {
return dp[start][end];
}
dp[start][end] = s.charAt(start) == s.charAt(end) && isPalin(s, start + 1, end - 1, dp);
return dp[start][end];
}
}
Version #1 Bottom-up DFS with memorization - SLOW
class Solution {
public List<List<String>> partition(String s) {
// TODO
return dfs(s, 0, new HashMap<>());
}
// Returns all the palindrome partition of substring [index, s.length())
private List<List<String>> dfs(String s, int index, Map<Integer, List<List<String>>> mem) {
// System.out.printf("index=%d, memsize=%d\n", index, mem.size());
if (index >= s.length()) {
return new ArrayList<>();
}
if (mem.containsKey(index)) {
return mem.get(index);
}
List<List<String>> result = new ArrayList<>();
for (int end = index + 1; end <= s.length(); end++) {
String word = s.substring(index, end);
// System.out.printf("word:%s\n", word);
if (isPalindrome(word)) {
if (end == s.length()) {
result.add(Arrays.asList(new String[]{word}));
}
List<List<String>> sub = dfs(s, end, mem);
for (List<String> su : sub) {
List<String> temp = new LinkedList<>(su);
temp.add(0, word);
result.add(temp);
}
}
}
mem.put(index, result);
return result;
}
private boolean isPalindrome(String s) {
int start = 0, end = s.length() - 1;
while (start < end) {
if (s.charAt(start) != s.charAt(end)) {
return false;
}
start++;
end--;
}
return true;
}
}
整体和之前写的一样，pruning的位置不一样了
我认为时间复杂度和空间复杂度都是 O(n^2)
时间复杂度是把 mem[n][n] fill out
96.11 %
class Solution {
public List<List<String>> partition(String s) {
List<List<String>> result = new ArrayList<>();
if (s == null) {
return result;
}
Boolean[][] mem = new Boolean[s.length()][s.length()];
helper(s, 0, mem, new ArrayList<>(), result);
return result;
}
private void helper(String s, int startIndex, Boolean[][] mem, List<String> path, List<List<String>> result) {
// Substring before startIndex has been partitioned into palindrome strings
// If we can reach the end of s, means the whole string is partitioned
if (startIndex == s.length()) {
result.add(new ArrayList<>(path));
return;
}
// [startIndex, endIndex]
for (int endIndex = startIndex; endIndex < s.length(); endIndex++) {
boolean isPalin = false;
if (mem[startIndex][endIndex] != null) {
isPalin = mem[startIndex][endIndex];
} else {
isPalin = isPalindrome(s, startIndex, endIndex);
mem[startIndex][endIndex] = isPalin;
}
if (isPalin) {
path.add(s.substring(startIndex, endIndex + 1));
helper(s, endIndex + 1, mem, path, result);
path.remove(path.size() - 1);
}
}
}
private boolean isPalindrome(String s, int startIndex, int endIndex) {
while (startIndex < endIndex) {
if (s.charAt(startIndex) != s.charAt(endIndex)) {
return false;
}
startIndex++;
endIndex--;
}
return true;
}
}
一刷
因为这里一个single character也可以作为palindrome, 所以没有办法用boolean array 做pruning, 因为所有的path都会是true
我用一个Boolean[][]记录check过的palindrome, 如果下一次遇到同样的startIndex和endIndex,就取之前的结果
时间复杂度？
O(n^2)??
public class Solution {
private Boolean[][] palindromeDict;
public List<List<String>> partition(String s) {
List<List<String>> result = new ArrayList<>();
if (s == null) return result;
//Boolean[i][j] string[i, j] isPalindrome or not
palindromeDict = new Boolean[s.length()][s.length()];
partitionDFSHelper(0, s, new ArrayList<String>(), result);
return result;
}
private void partitionDFSHelper(int startIndex, String s, List<String> path, List<List<String>> result) {
if (startIndex == s.length()) {
result.add(new ArrayList<String>(path));
}
for (int i = startIndex; i < s.length(); i++) {
if (isPalindrome(s, startIndex, i)) {
path.add(s.substring(startIndex, i + 1));
partitionDFSHelper(i + 1, s, path, result);
path.remove(path.size() - 1);
}
}
}
private boolean isPalindrome(String s, int start, int end) {
if (palindromeDict[start][end] != null) return palindromeDict[start][end];
while (start < end) {
if (s.charAt(start) != s.charAt(end)) {
palindromeDict[start][end] = false;
return false;
}
start++;
end--;
}
palindromeDict[start][end] = true;
return true;
}
}
No comments:
Post a Comment