131. 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"]
  ]

链接： http://leetcode.com/problems/palindrome-partitioning/

5/17/2017

算法班

照着别人的答案改的。10ms, 49%

还是要判断这种DFS + backtracking的做法到底每一步哪里是起点。这个不要与子集搞混。

 1 public class Solution {
 2     public List<List<String>> partition(String s) {
 3         List<List<String>> ret = new ArrayList<>();
 4         if (s == null || s.equals("")) {
 5             return ret;
 6         }
 7         List<String> list = new ArrayList<String>();
 8         partitionString(ret, s, list, 0);
 9         return ret;
10     }
11 
12     private void partitionString(List<List<String>> ret, String s, List<String> list, int pos) {
13         if (s.length() == pos) {
14             ret.add(new ArrayList<String>(list));
15         }
16         for (int i = pos + 1; i <= s.length(); i++) {
17             String substring = s.substring(pos, i);
18             if (isPalindrome(substring)) {
19                 list.add(substring);
20                 partitionString(ret, s, list, i);
21                 list.remove(list.size() - 1);
22             }
23         }
24     }
25 
26     private boolean isPalindrome(String s) {
27         for (int i = 0, j = s.length() - 1; i <= j; i++, j--) {
28             if (s.charAt(i) != s.charAt(j)) return false;
29         }
30         return true;
31     }
32 }

别人的解释

https://discuss.leetcode.com/topic/6186/java-backtracking-solution

DP解法

https://discuss.leetcode.com/topic/2884/my-java-dp-only-solution-without-recursion-o-n-2

Python一行

https://discuss.leetcode.com/topic/19370/1-liner-python-ruby

我的解法是每次传同样的string但是起点不同，但是也可以传不同的string就不用多传一个参数

https://discuss.leetcode.com/topic/16800/concise-java-solution