131. 分割回文串（和小李♥）

两种解法，发现用了回溯后跑分居然下降了。可能重复修改一条长list的代价要比重复构建list要大；也许python每次free了每层递归的local variable的内存。

解法1

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        results = []
        dfs(results, [], s, 0)
        return results

def dfs(results, path, s, index):
    if index == len(s):
        results.append(path)
        return
    for j in range(index+1, len(s)+1):
        sub = s[index:j]
        if is_palindrome(sub):
            dfs(results, path + [sub], s, j)

def is_palindrome(sub):
    return sub[::-1] == sub

解法二

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        results = []
        dfs(results, [], s, 0)
        return results

def dfs(results, path, s, index):
    if index == len(s):
        results.append([i for i in path])
        return
    for j in range(index+1, len(s)+1):
        sub = s[index:j]
        if is_palindrome(sub):
            path.append(sub)
            dfs(results, path, s, j)
            path.pop()

def is_palindrome(sub):
    return sub[::-1] == sub