Build a graph and DFS, a 120ms AC and dry python code


  • 0
    T
    class Solution:
    # @param s, a string
    # @return a list of lists of string
    def partition(self, s):
        graph = collections.defaultdict(set)
        n = len(s)
        for j in range(n):
            for i in range(j, n):
                if s[j:i+1] == s[j:i+1][::-1]:
                    graph[j].add(i+1)
        stack, res = [[0]], []
        while stack:
            route = stack.pop()
            node = route[-1]
            if node == n:
                res.append([s[j:i] for (j, i) in zip(route[:-1], route[1:])])
            for neighbor in graph[node]:
                stack.append(route+[neighbor])
        return res

Log in to reply
 

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