Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return
[
["aa","b"],
["a","a","b"]
]
Solution 0:
直接用DFS 做，实际上也是可以过Leetcode的检查的。
public List<List<String>> partition(String s) {
List<List<String>> ret = new ArrayList<List<String>>();
if (s == null) {
return ret;
}
dfs(s, 0, new ArrayList<String>(), ret);
return ret;
}
public static void dfs(String s, int index, List<String> path, List<List<String>> ret) {
int len = s.length();
if (index == len) {
ret.add(new ArrayList<String>(path));
return;
}
for (int i = index; i < len; i++) {
String sub = s.substring(index, i + 1);
if (!isPalindrome(sub)) {
continue;
}
path.add(sub);
dfs(s, i + 1, path, ret);
path.remove(path.size() - 1);
}
}
public static boolean isPalindrome(String s) {
int len = s.length();
int left = 0;
int right = len - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
Runtime: 520 ms
Solution 1:
用DFS 加上一个记忆。HashMap<String, Boolean> map 用它来记忆某一段是否回文，这样不用每一次都去判断回文。可以减少计算量。
public List<List<String>> partition1(String s) {
List<List<String>> ret = new ArrayList<List<String>>();
List<String> path = new ArrayList<String>();
if (s == null) {
return ret;
}
HashMap<String, Boolean> map = new HashMap<String, Boolean>();
dfs(s, path, ret, 0, map);
return ret;
}
public boolean isPalindrom(String s) {
int len = s.length();
if (len <= 1) {
return true;
}
int left = 0;
int right = len - 1;
for (; left < right; left++, right--) {
if (s.charAt(right) != s.charAt(left)) {
return false;
}
}
return true;
}
/*
we use a map to store the solutions to reduce the times of computing.
*/
public void dfs(String s, List<String> path, List<List<String>> ret, int index, HashMap<String, Boolean> map) {
if (index == s.length()) {
ret.add(new ArrayList<String>(path));
return;
}
for (int i = index; i < s.length(); i++) {
String sub = s.substring(index, i + 1);
Boolean flag = map.get(sub);
if (flag == null) {
flag = isPalindrom(sub);
map.put(sub, flag);
}
if (!flag) {
continue;
}
path.add(sub);
dfs(s, path, ret, i + 1, map);
path.remove(path.size() - 1);
}
}
2014.12.29 Redo:
不过，最后的runtime没有什么大的改善。可能是数据量太小！
// Solution 2: The DFS version with memory.
public List<List<String>> partition(String s) {
List<List<String>> ret = new ArrayList<List<String>>();
if (s == null) {
return ret;
} // bug: new map error.
dfs2(s, 0, new ArrayList<String>(), ret, new HashMap<String, Boolean>());
return ret;
} public static void dfs2(String s, int index, List<String> path, List<List<String>> ret, HashMap<String, Boolean> map) {
int len = s.length();
if (index == len) {
ret.add(new ArrayList<String>(path));
return;
} for (int i = index; i < len; i++) {
String sub = s.substring(index, i + 1);
if (!isPalindromeHash(sub, map)) {
continue;
} path.add(sub);
dfs2(s, i + 1, path, ret, map);
path.remove(path.size() - 1);
}
} // BUG 3: use boolean instead of Boolean.
public static boolean isPalindromeHash(String s, HashMap<String, Boolean> map) {
int len = s.length();
int left = 0;
int right = len - 1; if (map.get(s) != null) {
return map.get(s);
} map.put(s, true);
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
map.put(s, false);
return false;
}
left++;
right--;
} return true;
}
Runtime: 592 ms
Solution 2:
先用DP做一次判断是不是回文，然后再执行DFS，如果发现某条string不是回文，就可以直接退出，从而减少计算量。
public List<List<String>> partition(String s) {
List<List<String>> ret = new ArrayList<List<String>>();
List<String> path = new ArrayList<String>();
if (s == null) {
return ret;
}
boolean[][] isPalindrom = buildPalindromDP(s);
dfs2(s, path, ret, 0, isPalindrom);
return ret;
}
/*
* Solution 2: Use DP to reduce the duplicate count.
* */
boolean[][] buildPalindromDP(String s) {
int len = s.length();
boolean[][] D = new boolean[len][len];
for (int j = 0; j < len; j++) {
for (int i = 0; i <= j; i++) {
if (j == 0) {
D[i][j] = true;
continue;
}
D[i][j] = s.charAt(i) == s.charAt(j)
&& (j - i <= 2 || D[i + 1][j - 1]);
}
}
return D;
}
/*
we use a map to store the solutions to reduce the times of computing.
*/
public void dfs2(String s, List<String> path, List<List<String>> ret, int index, boolean[][] isPalindromDP) {
if (index == s.length()) {
ret.add(new ArrayList<String>(path));
return;
}
for (int i = index; i < s.length(); i++) {
String sub = s.substring(index, i + 1);
if (!isPalindromDP[index][i]) {
continue;
}
path.add(sub);
dfs2(s, path, ret, i + 1, isPalindromDP);
path.remove(path.size() - 1);
}
}
2014.12.29 Redo:
// BUG 3: use boolean instead of Boolean.
public static boolean isPalindromeHash(String s, HashMap<String, Boolean> map) {
int len = s.length();
int left = 0;
int right = len - 1; if (map.get(s) != null) {
return map.get(s);
} map.put(s, true);
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
map.put(s, false);
return false;
}
left++;
right--;
} return true;
} // Solution 3: Use DP to determine the palindrome first.
public List<List<String>> partition(String s) {
List<List<String>> ret = new ArrayList<List<String>>();
if (s == null) {
return ret;
} int len = s.length(); // D[i][j]: if this a palindrom for s.substring(i, j + 1).
boolean[][] D = new boolean[len][len]; for (int j = 0; j < len; j++) {
for (int i = 0; i <= j; i++) {
D[i][j] = s.charAt(i) == s.charAt(j) && (j - i <= 2 || D[i + 1][j - 1]);
}
} // bug: new map error.
dfs3(s, 0, new ArrayList<String>(), ret, D);
return ret;
} public static void dfs3(String s, int index, List<String> path, List<List<String>> ret, boolean[][] D) {
int len = s.length();
if (index == len) {
ret.add(new ArrayList<String>(path));
return;
} for (int i = index; i < len; i++) {
String sub = s.substring(index, i + 1);
if (!D[index][i]) {
continue;
} path.add(sub);
dfs3(s, i + 1, path, ret, D);
path.remove(path.size() - 1);
}
}
Runtime: 524 ms, 实际上运行时间也没多少改善。可能是数据集大小的问题咯。
GitHub Link:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/dfs/Partition_2014_1229.java