648. Replace Words

Medium (Trung bình) Python 🔗 Xem trên LeetCode

📋 Đề Bài

In English, we have a concept called root, which can be followed by some other word to form another longer word - let's call this word successor. For example, when the root "an" is followed by the successor word "other", we can form a new word "another".

Given a dictionary consisting of many roots and a sentence consisting of words separated by spaces, replace all the successors in the sentence with the root forming it. If a successor can be replaced by more than one root, replace it with the root that has the shortest length.

Return the sentence after the replacement.

 

Example 1:

Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

Example 2:

Input: dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
Output: "a a b c"

 

Constraints:

  • 1 <= dictionary.length <= 1000
  • 1 <= dictionary[i].length <= 100
  • dictionary[i] consists of only lower-case letters.
  • 1 <= sentence.length <= 106
  • sentence consists of only lower-case letters and spaces.
  • The number of words in sentence is in the range [1, 1000]
  • The length of each word in sentence is in the range [1, 1000]
  • Every two consecutive words in sentence will be separated by exactly one space.
  • sentence does not have leading or trailing spaces.

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

Hash Table (Bảng băm)Trie (Cây tiền tố)
⏱️ Thời gian O(n²)
💾 Không gian O(n)

💻 Lời Giải

Python 0648-replace-words.py 
class Node:
    def __init__(self):
        self.isEndWord = False
        self.children = defaultdict(Node)

class Trie:
    def __init__(self):
        self.root = Node()
        
    def insert(self, word: str) -> None:
        root = self.root
        for char in word:
            root = root.children[char]
        root.isEndWord = True
        
    def replace(self, word: str) -> str:
        root = self.root
        repWord = ''
        for char in word:
            repWord += char
            if char not in root.children:
                return word
            if root.children[char].isEndWord:
                return repWord
            root = root.children[char]
        return word
        

class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        sentence = sentence.split()
        trie = Trie()
        
        for word in dictionary:
            trie.insert(word)
        
        n = len(sentence)
        
        for i in range(n):
            sentence[i] = trie.replace(sentence[i])
            
        return ' '.join(sentence)