```
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: Set[str]
:rtype: bool
"""
l = len(s)
match = [0]
for i in xrange(1, l + 1):
for j in reversed(match):
if s[j:i] in wordDict:
match.append(i)
break
return match[-1] == l
```

If s[:i] can be matched successfully, i is added into "match".

s[:i] can be matched if and only if there exists j < i and j in "match" such that s[j:i] is in wordDict.