Python ONE LINE solution 42 ms


  • 0
    L

    Since wordDict is not a list but a set, two lines are required. But you get the idea.

    class Solution(object):
            
        def wordBreak(self, s, wordDict):
            """
            :type s: str
            :type wordDict: List[str]
            :rtype: bool
            """
            wd = set(wordDict)
            return reduce(lambda dp, i: dp + [i] if any(s[j:i] in wd for j in dp) else dp, range(1,len(s) + 1), [0])[-1] == len(s)
    

    The very long one line is building a list such that each element is the length of a subtring of s starting from beginning that can be broken down into words. Each time given a new length of the substring (i), the lambda function checks for any breakable substring with length j < i if the string s[j:i] is in the dictionary. If it is, then i is also breakable and added to the list. Checking the last breakable length equals to the length of s gives the answer.


Log in to reply
 

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