首页 > 代码库 > LeetCode: Palindrome Partitioning 解题报告
LeetCode: 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.
For example, given s = "aab",
Return
[
["aa","b"],
["a","a","b"]
]
Solution 0:
直接用DFS 做，实际上也是可以过Leetcode的检查的，主页君就不在这里写了。
Solution 1:
用DFS 加上一个记忆。HashMap<String, Boolean> map 用它来记忆某一段是否回文，这样不用每一次都去判断回文。可以减少计算量。
1 public List<List<String>> partition1(String s) { 2 List<List<String>> ret = new ArrayList<List<String>>(); 3 List<String> path = new ArrayList<String>(); 4 5 if (s == null) { 6 return ret; 7 } 8 9 HashMap<String, Boolean> map = new HashMap<String, Boolean>();10 11 dfs(s, path, ret, 0, map);12 13 return ret;14 }15 16 public boolean isPalindrom(String s) {17 int len = s.length();18 if (len <= 1) {19 return true;20 }21 22 int left = 0;23 int right = len - 1;24 for (; left < right; left++, right--) {25 if (s.charAt(right) != s.charAt(left)) {26 return false;27 }28 }29 30 return true;31 }32 33 /*34 we use a map to store the solutions to reduce the times of computing.35 */36 public void dfs(String s, List<String> path, List<List<String>> ret, int index, HashMap<String, Boolean> map) {37 if (index == s.length()) {38 ret.add(new ArrayList<String>(path));39 return;40 }41 42 for (int i = index; i < s.length(); i++) {43 String sub = s.substring(index, i + 1);44 45 Boolean flag = map.get(sub);46 if (flag == null) {47 flag = isPalindrom(sub);48 map.put(sub, flag);49 }50 51 if (!flag) {52 continue;53 }54 55 path.add(sub);56 dfs(s, path, ret, i + 1, map);57 path.remove(path.size() - 1);58 }59 }
Solution 2:
先用DP做一次判断是不是回文，然后再执行DFS，如果发现某条string不是回文，就可以直接退出，从而减少计算量。
1 public List<List<String>> partition(String s) { 2 List<List<String>> ret = new ArrayList<List<String>>(); 3 List<String> path = new ArrayList<String>(); 4 5 if (s == null) { 6 return ret; 7 } 8 9 boolean[][] isPalindrom = buildPalindromDP(s);10 11 dfs2(s, path, ret, 0, isPalindrom);12 13 return ret;14 }15 16 /*17 * Solution 2: Use DP to reduce the duplicate count.18 * */19 boolean[][] buildPalindromDP(String s) {20 int len = s.length();21 boolean[][] D = new boolean[len][len];22 23 for (int j = 0; j < len; j++) {24 for (int i = 0; i <= j; i++) {25 if (j == 0) {26 D[i][j] = true;27 continue;28 } 29 30 D[i][j] = s.charAt(i) == s.charAt(j) 31 && (j - i <= 2 || D[i + 1][j - 1]);32 }33 }34 35 return D;36 }37 38 /*39 we use a map to store the solutions to reduce the times of computing.40 */41 public void dfs2(String s, List<String> path, List<List<String>> ret, int index, boolean[][] isPalindromDP) {42 if (index == s.length()) {43 ret.add(new ArrayList<String>(path));44 return;45 }46 47 for (int i = index; i < s.length(); i++) {48 String sub = s.substring(index, i + 1);49 if (!isPalindromDP[index][i]) {50 continue;51 }52 53 path.add(sub);54 dfs2(s, path, ret, i + 1, isPalindromDP);55 path.remove(path.size() - 1);56 }57 }
GitHub Link:
Partition.java
LeetCode: Palindrome Partitioning 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。