Python easy to understand backtracking solution.


  • 2
    C
    def partition(self, s):
        res = []
        self.dfs(s, [], res)
        return res
        
    def dfs(self, s, path, res):
        if not s: # backtracking
            res.append(path)
        for i in xrange(1, len(s)+1):
            if self.isPar(s[:i]):
                self.dfs(s[i:], path+[s[:i]], res)
                
    def isPar(self, s):
        return s == s[::-1]

  • 1
    C

    Here is a revised version with comments:

    def partition(self, s):
        res = []
        self.dfs(s, [], res)
        return res
        
    def dfs(self, s, path, res):
        if not s:
            res.append(path[:])  # take care here
            return  # backtracking
        for i in xrange(1, len(s)+1):
            if self.isPar(s[:i]):
                path.append(s[:i])
                self.dfs(s[i:], path, res)
                path.pop() # simulate stack here
                
    def isPar(self, s):
        return s == s[::-1]
    

  • 0
    H

    The revised version is great!


  • 0
    H

    I cannot see the difference between these two version, why should we simulate a stack here? and why should we replace path with path[:]? could you please give me a hint? Thanks..


  • 0
    L

    Hi caikehe,

    I am also confused about the difference between path and path[:]. I have tried path, and it will return empty result.. Thanks!


  • 2
    C

    If you use path, the elements in it willl be updated automatically, If we use path[:], we just append the current elements in it.


  • 1
    L

    I have some discussion in other similar issue, and I think the reason should be that if we use path during the recursive function call, it will use the reference of path, so if path is modified later, the content of res will be updated as well. Thus we will get empty list in the end.

    But if we use path[:], it will create a new list and append it to res. The change of path will not affect the content of res


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.