A python solution using DP + bounded search beats 99.76%


  • 0
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        # use dictionary for faster check
        # only the length of the words in the wordDict
        # can be considered as a 'step'
        wordDic = {}
        lengths = {}
        for w in wordDict:
           wordDic[w] = True
           lengths[len(w)] = True
        reach = [False for _ in range(len(s))]
        
        # use DP to update the reachability for position i
        # only check previous possible positions within a 'step'
        for i in range(len(s)):
            for j in lengths:
                if i-j+1>=0:
                    if s[i-j+1:i+1] in wordDic and (i-j+1==0 or reach[i-j]):
                        reach[i] = True
                        break
        return reach[len(s)-1]
    

    Runtime: 38 ms


Log in to reply
 

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