题目描述（中等难度）

131. Palindrome Partitioning - 图1

给一个字符串，然后在任意位置切割若干次，保证切割后的每个字符串都是回文串。输出所有满足要求的切割结果。

解法一 分治

将大问题分解为小问题，利用小问题的结果，解决当前大问题。

这道题的话，举个例子。

  1. aabb
  2. 先考虑在第 1 个位置切割，a | abb
  3. 这样我们只需要知道 abb 的所有结果，然后在所有结果的头部把 a 加入
  4. abb 的所有结果就是 [a b b] [a bb]
  5. 每个结果头部加入 a，就是 [a a b b] [a a bb]
  7. aabb
  8. 再考虑在第 2 个位置切割，aa | bb
  9. 这样我们只需要知道 bb 的所有结果，然后在所有结果的头部把 aa 加入
  10. bb 的所有结果就是 [b b] [bb]
  11. 每个结果头部加入 aa,就是 [aa b b] [aa bb]
  13. aabb
  14. 再考虑在第 3 个位置切割，aab|b
  15. 因为 aab 不是回文串，所有直接跳过
  17. aabb
  18. 再考虑在第 4 个位置切割，aabb |
  19. 因为 aabb 不是回文串，所有直接跳过
  21. 最后所有的结果就是所有的加起来
  22. [a a b b] [a a bb] [aa b b] [aa bb]

然后中间的过程求 abb 的所有结果，求 aab 的所有结果等等，就可以递归的去求。递归出口的话，就是空串的所有子串就是一个空的list 即可。

  1. public List<List<String>> partition(String s) {
  2.     return partitionHelper(s, 0);
  3. }
  5. private List<List<String>> partitionHelper(String s, int start) {
  6.     //递归出口，空字符串
  7.     if (start == s.length()) {
  8.         List<String> list = new ArrayList<>();
  9.         List<List<String>> ans = new ArrayList<>();
  10.         ans.add(list);
  11.         return ans;
  12.     }
  13.     List<List<String>> ans = new ArrayList<>();
  14.     for (int i = start; i < s.length(); i++) {
  15.         //当前切割后是回文串才考虑
  16.         if (isPalindrome(s.substring(start, i + 1))) {
  17.             String left = s.substring(start, i + 1);
  18.             //遍历后边字符串的所有结果，将当前的字符串加到头部
  19.             for (List<String> l : partitionHelper(s, i + 1)) {
  20.                 l.add(0, left);
  21.                 ans.add(l);
  22.             }
  23.         }
  25.     }
  26.     return ans;
  27. }
  29. private boolean isPalindrome(String s) {
  30.     int i = 0;
  31.     int j = s.length() - 1;
  32.     while (i < j) {
  33.         if (s.charAt(i) != s.charAt(j)) {
  34.             return false;
  35.         }
  36.         i++;
  37.         j--;
  38.     }
  39.     return true;
  40. }

分治的话，一般情况下都可以利用动态规划的思想改为迭代的形式。递归就是压栈压栈，然后到达出口就出栈出栈出栈。动态规划就可以把压栈的过程省去，直接从递归出口往回考虑。之前做过很多题了，可以参考 77题、91 题、115 题 等等，都是一样的思想。这道题修改的话，看完解法二的优化后可以参考 这里>) 的代码。

解法二 分治优化

每次判断一个字符串是否是回文串的时候，我们都会调用 isPalindrome 判断。这就会造成一个问题，比如字符串 abbbba，期间我们肯定会判断 bbbb 是不是回文串，也会判断 abbbba 是不是回文串。判断 abbbba 是不是回文串的时候，在 isPalindrome 中依旧会判断中间的 bbbb 部分。而其实如果我们已经知道了 bbbb 是回文串，只需要判断 abbbba 的开头和末尾字符是否相等即可。

所以我们为了避免一些重复判断，可以用动态规划的方法，把所有字符是否是回文串提前存起来。

对于字符串 s。

用 dp[i][j] 表示 s[i，j] 是否是回文串。

然后有 dp[i][j] = s[i] == s[j] && dp[i+1][j-1] 。

我们只需要两层 for 循环，从每个下标开始，考虑所有长度的子串即可。

  1. boolean[][] dp = new boolean[s.length()][s.length()];
  2. int length = s.length();
  3. //考虑所有长度的子串
  4. for (int len = 1; len <= length; len++) {
  5.     //从每个下标开始
  6.     for (int i = 0; i <= s.length() - len; i++) {
  7.         int j = i + len - 1;
  8.         dp[i][j] = s.charAt(i) == s.charAt(j) && (len < 3 || dp[i + 1][j - 1]);
  9.     }
  10. }

因为要保证 dp[i + 1][j - 1] 中 i + 1 <= j - 1，

  1. i + 1 <= j - 1
  2. 把 j = i + len - 1 代入上式
  3. i + 1 <= i + len - 1 - 1
  4. 化简得
  5. len >= 3

所以为了保证正确，多加了 len < 3 的条件。也就意味着长度是 1 和 2 的时候，我们只需要判断 s[i] == s[j]。

然后把 dp 传入到递归函数中即可。

  1. public List<List<String>> partition(String s) {
  2.     boolean[][] dp = new boolean[s.length()][s.length()];
  3.     int length = s.length();
  4.     for (int len = 1; len <= length; len++) {
  5.         for (int i = 0; i <= s.length() - len; i++) {
  6.             int j = i + len - 1;
  7.             dp[i][j] = s.charAt(i) == s.charAt(j) && (len < 3 || dp[i + 1][j - 1]);
  8.         }
  9.     }
  10.     return partitionHelper(s, 0, dp);
  11. }
  13. private List<List<String>> partitionHelper(String s, int start, boolean[][] dp) {
  14.     if (start == s.length()) {
  15.         List<String> list = new ArrayList<>();
  16.         List<List<String>> ans = new ArrayList<>();
  17.         ans.add(list);
  18.         return ans;
  19.     }
  20.     List<List<String>> ans = new ArrayList<>();
  21.     for (int i = start; i < s.length(); i++) {
  22.         if (dp[start][i]) {
  23.             String left = s.substring(start, i + 1);
  24.             for (List<String> l : partitionHelper(s, i + 1, dp)) {
  25.                 l.add(0, left);
  26.                 ans.add(l);
  27.             }
  28.         }
  30.     }
  31.     return ans;
  32. }

解法三 回溯

115 题 中考虑了分治、回溯、动态规划，这道题同样可以用回溯法。

回溯法其实就是一个 dfs 的过程，同样举个例子。

  1. aabb
  2. 先考虑在第 1 个位置切割，a | abb
  3. 把 a 加入到结果中 [a]
  5. 然后考虑 abb
  6. 先考虑在第 1 个位置切割，a | bb
  7. 把 a  加入到结果中 [a a]
  9. 然后考虑 bb
  10. 先考虑在第 1 个位置切割，b | b
  11. 把 b 加入到结果中 [a a b] 
  13. 然后考虑 b
  14. 先考虑在第 1 个位置切割，b | 
  15. 把 b 加入到结果中 [a a b b] 
  17. 然后考虑空串
  18. 把结果加到最终结果中 [[a a b b]]
  20. 回溯到上一层 
  21. 考虑 bb
  22. 考虑在第 2 个位置切割，bb |
  23. 把 bb 加入到结果中 [a a bb] 
  25. 然后考虑 空串
  26. 把结果加到最终结果中 [[a a b b] [a a bb]]
  28. 然后继续回溯

可以看做下边的图做 dfs ，而每一层其实就是当前字符串所有可能的回文子串。

131. Palindrome Partitioning - 图2

就是很经典的回溯法，一个 for 循环，添加元素，递归，删除元素。这里判断是否是回文串，我们就直接用 dp 数组。

  1. public List<List<String>> partition(String s) {
  2.     boolean[][] dp = new boolean[s.length()][s.length()];
  3.     int length = s.length();
  4.     for (int len = 1; len <= length; len++) {
  5.         for (int i = 0; i <= s.length() - len; i++) {
  6.             dp[i][i + len - 1] = s.charAt(i) == s.charAt(i + len - 1) && (len < 3 || dp[i + 1][i + len - 2]);
  7.         }
  8.     }
  9.     List<List<String>> ans = new ArrayList<>();
  10.     partitionHelper(s, 0, dp, new ArrayList<>(), ans);
  11.     return ans;
  12. }
  14. private void partitionHelper(String s, int start, boolean[][] dp, List<String> temp, List<List<String>> res) {
  15.     //到了空串就加到最终的结果中
  16.     if (start == s.length()) {
  17.         res.add(new ArrayList<>(temp));
  18.     }
  19.     //在不同位置切割
  20.     for (int i = start; i < s.length(); i++) {
  21.         //如果是回文串就加到结果中
  22.         if (dp[start][i]) {
  23.             String left = s.substring(start, i + 1);
  24.             temp.add(left);
  25.             partitionHelper(s, i + 1, dp, temp, res);
  26.             temp.remove(temp.size() - 1);
  27.         }
  29.     }
  30. }

总

这道题没有什么新内容了，就是分治、回溯、动态规划，很常规的题目了。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情