How hard is LeetCode 140. Word Break II?

LeetCode 140. Word Break II is rated Hard on LeetCode.

What is the time complexity of LeetCode 140. Word Break II?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 140. Word Break II?

The Python solution on this page uses O(n) auxiliary space.

Word Break II — LeetCode 140 Python Solution

HardTrieMemoizationArrayHash TableStringDynamic ProgrammingBacktracking

Problem: #140
Pattern: Trie
Reading time: 7 min
Source: leetcode.com

The problem

Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.

Example

Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]

Python solution

Python

class Trie:
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False

    def insert(self, word):
        node = self
        for c in word:
            idx = ord(c) - ord('a')
            if node.children[idx] is None:
                node.children[idx] = Trie()
            node = node.children[idx]
        node.is_end = True

    def search(self, word):
        node = self
        for c in word:
            idx = ord(c) - ord('a')
            if node.children[idx] is None:
                return False
            node = node.children[idx]
        return node.is_end


class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        def dfs(s):
            if not s:
                return [[]]
            res = []
            for i in range(1, len(s) + 1):
                if trie.search(s[:i]):
                    for v in dfs(s[i:]):
                        res.append([s[:i]] + v)
            return res

        trie = Trie()
        for w in wordDict:
            trie.insert(w)
        ans = dfs(s)
        return [' '.join(v) for v in ans]

Complexity

Measure	Complexity
Time	O(n)
Space	O(n) auxiliary

Pattern: Trie

Store a set of words by their shared prefixes so lookups cost the length of the word. LeetCode 140. Word Break II 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.

Frequently asked questions

How hard is LeetCode 140. Word Break II?: LeetCode 140. Word Break II is rated Hard on LeetCode.
What is the time complexity of LeetCode 140. Word Break II?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 140. Word Break II?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 140. Word Break II cover?: LeetCode 140. Word Break II is tagged Trie, Memoization, Array, Hash Table, String, Dynamic Programming and Backtracking on LeetCode.