140. Word Break II

📋 Đề Bài

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.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

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

Example 2:

Input: s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"]
Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

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

Constraints:

1 <= s.length <= 20
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 10
s and wordDict[i] consist of only lowercase English letters.
All the strings of wordDict are unique.

🧠 Thuật Toán & Kỹ Thuật

DFS (Tìm kiếm theo chiều sâu)Hash Table (Bảng băm)Union Find (Tập hợp rời rạc)Trie (Cây tiền tố)

⏱️ Thời gian O(V+E)

💾 Không gian O(V)

💻 Lời Giải

Python 0140-word-break-ii.py

class TrieNode:
    def __init__(self):
        self.isEndWord = False
        self.children = defaultdict(TrieNode)
        
class Trie:
    def __init__(self):
        self.root = TrieNode()
        
    def insert(self, word: str) -> None:
        root = self.root
        for char in word:
            root = root.children[char]
        root.isEndWord = True
        
    def find(self, word: str) -> None:
        root = self.root
        for char in word:
            if char not in root.children:
                return False
            root = root.children[char]
        return root.isEndWord

    def dfs(self, s: str, path: str, i: int) -> List[str]:
        if i == len(s):
            return [path[:-1]]
        ans = []
        for j in range(i + 1, len(s) + 1):
            sp = s[i:j]
            if self.find(sp):
                ans += self.dfs(s, path + sp + ' ', j)
        return ans
        
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        trie = Trie()
        
        for word in wordDict:
            trie.insert(word)
            
        return trie.dfs(s, '', 0)