A python DFS solution


  • 0
    L
    class Solution(object):
        def wordBreak(self, s, wordDict):
            """
            :type s: str
            :type wordDict: List[str]
            :rtype: bool
            """
            def dfs(i):
                if i in dic:
                    return dic[i]
                dic[i]=False
                for j in xrange(i+1,min(len(s)+1,i+lens+1)):
                    if s[i:j] in wordSet and dfs(j):
                        dic[i]=True
                        break
                return dic[i]
            if not s or not wordDict:
                return False
            wordSet=set(wordDict)
            lens=max(len(x) for x in wordSet)
            dic={len(s):True}
            return dfs(0)
    

Log in to reply
 

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