HardNo. 0140
Word Break II — LeetCode 140 Python Solution
- Pattern
- Trie
- Topics
- Trie, Memoization, Array, Hash Table, String, Dynamic Programming, Backtracking
- 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
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
- Time
- O(n)
- Space · auxiliary
- O(n)
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.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0139 | Word Break | Medium |
| 0691 | Stickers to Spell Word | Hard |
| 0792 | Number of Matching Subsequences | Medium |
| 1255 | Maximum Score Words Formed by Letters | Hard |
| 2019 | The Score of Students Solving Math Expression | Hard |
| 2707 | Extra Characters in a String | Medium |
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.