Concise Python and some optimization


  • 1
    M

    My idea is to keep a list of possible start positions. At first, there is only one element, position 0, in it. Then, I search the string s and when a word is found in the wordDict, I add the position after that word into the start list meaning this is another possible start position.

    def wordBreak(self, s, wordDict):
        starts, e = [0], 1
        wordDict = set(wordDict)
        while e <= len(s):
            for start in starts:
                if s[start: e] in wordDict:
                    starts.append(e)
                    break
            e += 1
        return starts[-1] == len(s)
    

    And here I did some optimization, if the length of the longest word in wordDict is less than the length of a start position to current position, I delete that start position from the list:

    def wordBreak(self, s, wordDict):
        if not wordDict:
            return False
        starts, e = [0], 1
        wordDict = set(wordDict)
        longest = max([len(w) for w in wordDict])
        while e <= len(s):
            for start in starts:
                if s[start: e] in wordDict:
                    starts.append(e)
                    break
            e += 1
            if not starts:
                if e > longest:
                    return False
            else:
                if e - starts[0] > longest:
                     starts.pop(0)
        return starts != [] and starts[-1] == len(s)
    

Log in to reply
 

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