Straight forward python implementation with DP, 40ms beats 90%


  • 0
    I
    class Solution(object):
        def wordBreak(self, s, wordDict):
            memo=set()
            # wordLen is the list of word length
            wordLen=sorted(set(map(len,wordDict)))
            def search(sub):
                if sub in wordDict:
                    return True
                if sub in memo:
                    return False
                for i in wordLen:
                    if sub[:i] in wordDict:
                        if search(sub[i:]):
                            return True
                memo.add(sub)
                return False
            return search(s)

Log in to reply
 

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