首页 > 代码库 > 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     }
View Code

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     }
View Code

GitHub Link:

Partition.java

LeetCode: Palindrome Partitioning 解题报告