Word Break — LeetCode 139 Python Solution

The problem

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example

Input

s = "leetcode", wordDict = ["leet","code"]

Output

true

Explanation

Return true because "leetcode" can be segmented as "leet code".

Python solution

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        words = set(wordDict)
        n = len(s)
        f = [True] + [False] * n
        for i in range(1, n + 1):
            f[i] = any(f[j] and s[j:i] in words for j in range(i))
        return f[n]

Complexity

Pattern: Trie

Store a set of words by their shared prefixes so lookups cost the length of the word. LeetCode 139. Word Break is filed here because LeetCode tags it Trie, which is the vocabulary this hub collects.

The trie guide has the Python template for the pattern and the 49 LeetCode problems that use it.

Related problems