36 ms Python Solution with Explanation

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

Log in to reply

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