# 0131. Palindrome Partitioning
###### tags: `Leetcode` `Medium` `Backtracking` `DFS`
Link: https://leetcode.com/problems/palindrome-partitioning/
## 思路
### 思路一 Pure Backtracking $O(N*2^N)$ $O(N)$
从start pos开始找出所有可能的子字串，一个一个检查是不是palindrome，如果是就加进答案，继续遍历
Each substring will take $O(N)$ time to check if it's palindrom and $O(N)$ time to generate substring from start to end indexes. 所以实际上是$O(2N*2^N)$
### 思路二 Backtracking+Dynamic Programming $O(N*2^N)$ $O(N)$
先用dp table记录所有palindrome，这样就不需要重复遍历了
for each palindrom we still need $O(N)$ time to generate substring from start to end indexes. The complexity is still the same $O(N*2^N)$ 但是会更省时间，因为是$O(N*2^N)$

## Code
### 思路一

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        ans = []

        def isPalindrome(start, end):
            left, right = start, end
            while left<right:
                if s[left]!=s[right]:
                    return False
                left += 1
                right -= 1
            return True

        def backtracking(curr, start):
            if start == len(s): 
                ans.append(curr[:])
            else:
                for i in range(start, len(s)):
                    if isPalindrome(start, i):
                        curr.append(s[start:i+1])
                        backtracking(curr, i+1)
                        curr.pop()
                
        backtracking([], 0)
        return ans

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> ans = new ArrayList<>();
        List<String> result = new ArrayList<>();
        backtracking(ans, result, 0, s);
        return ans;
    }
    private void backtracking(List<List<String>> ans, List<String> result, int start, String s){
        if(start == s.length()){
            ans.add(new ArrayList<String>(result));
            return;
        }
        for(int i = start;i < s.length();i++){
            if(isPalindrome(s,start,i)){
                result.add(s.substring(start, i+1));
                backtracking(ans, result, i+1, s);
                result.remove(result.size()-1);
            }
        }
    }
    private boolean isPalindrome(String s, int start, int end){
        if(start==end) return true;
        while(start<end){
            if(s.charAt(start)!=s.charAt(end)) return false;
            start++;
            end--;
        }
        return true;
    }
}

### 思路二

class Solution {
    List<List<String>> ans;
    public List<List<String>> partition(String s) {
        ans = new ArrayList<>();
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for(int i=0; i<n; i++) dp[i][i] = true;
        for(int len=2; len<=n; len++){
            for(int i=0; i+len-1<n; i++){
                int j = i+len-1;
                if(s.charAt(i)==s.charAt(j)){
                    if(j==i+1) dp[i][j] = true;
                    else if(dp[i+1][j-1]) dp[i][j] = true;
                }
            }
        }
        
        List<String> curr = new ArrayList<>();
        dfs(s, 0, dp, curr);
        return ans;
    }
    private void dfs(String s, int start, boolean[][] dp, List<String> curr){
        if(start>=s.length()){
            ans.add(new ArrayList<>(curr));
        }
        for(int i=start; i<s.length(); i++){
            if(!dp[start][i]) continue;
            curr.add(s.substring(start, i+1));
            dfs(s, i+1, dp, curr);
            curr.remove(curr.size()-1);
        }
    }
}