36 ms Python Solution with Explanation


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


Log in to reply
 

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