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

Java(backtrack, O(N*2^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)