Compact Python solution

  • 1
    class Solution(object):
        def wordBreak(self, s, wordDict):
            self.words = wordDict
            self.table = {'':['']}
            return self.backtrack(s)
        def backtrack(self, s):
            if s in self.table:
                return self.table[s]
            sols = []
            for word in self.words:
                if word == s[:len(word)]:
                    for sol in self.backtrack(s[len(word):]):
                        sols.append(word+' '+sol if sol else word)
            self.table[s] = sols
            return sols

Log in to reply

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