# DP Solution with Length Optimization Beating 97% in Python

• 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: