DP Solution with Length Optimization Beating 97% in Python


  • 1

    First, I traversal all the words in the wordDict and find the lengths of those words and store all the lengths in the lengthSet;

    Then, I initialize the matchPoint set, which only contains 0. That is, we start matching with the substring from the first character of s

    Every time in the main loop, I pop out a matchPoint from the set, and for each length in the lengthSet, check whether s[startPoint: startPoint+length] is in the wordDict:

    1. if the substring is in the wordDict, add the new endPoint into the startPoint
    2. if the substring is not in the wordDict, skip it and check the next length
      If the new endPoint is equal to the length of s, then we could claim that s can be broken into several words;

    Instead traversal all the word in the wordDict as other solutions do, I traverse the length of the word in the wordDict and check whether s[startPoint: startPoint+length] is in the wordDict
    Instead using a DP list as other solutions do, I use a DP set to store the startPoint.

    class Solution(object):
        def wordBreak(self, s, wordDict):
            """
            :type s: str
            :type wordDict: List[str]
            :rtype: bool
            """
            lengthSet = set([len(word) for word in wordDict])
            wordSet = set(wordDict)
            matchPoint = {0}
            
            while matchPoint:
                startPoint = matchPoint.pop()
                for length in lengthSet:
                    endPoint = startPoint + length
                    thisString = s[startPoint: endPoint]
                    if thisString in wordSet:
                        matchPoint.add(endPoint)
                        if endPoint == len(s):
                            return True
            return False
    

  • 0
    P

    Awesome finding..... Very nice solution...
    We can also use minimum length and maximum length of the string in the dictionary for optimization


Log in to reply
 

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