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]
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]
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..
I am also confused about the difference between path and path[:]. I have tried path, and it will return empty result.. Thanks!
If you use path, the elements in it willl be updated automatically, If we use path[:], we just append the current elements in it.
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
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.