131. Palindrome Partitioning

# Medium

回文子集：一个string的substring的集合中所有元素都是回文（正反读都是一样的），substring里的字母都不重复

Solution:

定义一个subs为string类型，相当于子集集合里的每个字符串，每次多加一个字母，判断是否是回文，不是的话继续加一个后面的字母，如果是回文，就加入子集集合中。若是碰到了return就回溯到是回文的状态，尝试别的可能的组合。

sub = '' 非常需要思考放在哪里？遗留问题。

helper函数的终止条件if index == len(s)

Python

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        res = []
        self.backtrack(s, 0, [], res)
        return res
        
    def backtrack(self, s, start, level, res):
        # add to res
        if start == len(s):
            res.append(level[:])
            
        for i in range(start+1, len(s)+1):
            subString = s[start:i]
            if self.isPalindrome(subString):
                level.append(subString)
                print(level)
                self.backtrack(s, i, level, res)
                level.pop()
        
    def isPalindrome(self, subString):
        for i in range(len(subString)//2):
            if subString[i] != subString[len(subString) - i -1]:
                return False
            
        return True

Process

Input: "aabcd"

Stdout: [["a","a","b","c","d"],["aa","b","c","d"]]

Output:level(before adding new element), subs(may be added to level)

[] a

['a'] a

['a', 'a'] b

['a', 'a', 'b'] c

['a', 'a', 'b', 'c'] d

['a', 'a', 'b'] cd

['a', 'a'] bc

['a', 'a'] bcd

['a'] ab

['a'] abc

['a'] abcd

[] aa

['aa'] b

['aa', 'b'] c

['aa', 'b', 'c'] d

['aa', 'b'] cd

['aa'] bc

['aa'] bcd

[] aab

[] aabc

[] aabcd

Java(backtrack, O(N*2^N)

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

// for each element, decide cut or not, so the complexity is 2^n
// for each palindrome, judge it's palindrome or not, takes n

string = string[:-1] is to delete the last element of a string;

list.pop() is to delete the last element of a list

can sacrifice space to compute isParlindrome before backtracking, T = O(2^n)