Leetcdoe 131. Palindrome Partitioning

https://leetcode.com/problems/palindrome-partitioning/

Maybe there are other better ways, while DFS is the one easy to get and acceptable.

Solution:

# T:O(2^n) S:O(n)
class Solution:
    # @param s, a string
    # @return a list of lists of string
    def isPalindrome(self, s):
        for i in range(len(s)/2):
            if s[i] != s[len(s)-1-i]: return False
        return True
    
    def dfs(self, s, stringlist):
        if len(s) == 0: Solution.res.append(stringlist)
        for i in range(1, len(s)+1):
            if self.isPalindrome(s[:i]):
                self.dfs(s[i:], stringlist+[s[:i]])
            
    def partition(self, s):
        Solution.res = []
        self.dfs(s, [])
        return Solution.res

Run Time: 244 ms