Welcome to Subscribe On Youtube

648. Replace Words

Description

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.

Solutions

  • class Trie { private Trie[] children = new Trie[26]; private int ref = -1; public void insert(String w, int i) { Trie node = this; for (int j = 0; j < w.length(); ++j) { int idx = w.charAt(j) - 'a'; if (node.children[idx] == null) { node.children[idx] = new Trie(); } node = node.children[idx]; } node.ref = i; } public int search(String w) { Trie node = this; for (int j = 0; j < w.length(); ++j) { int idx = w.charAt(j) - 'a'; if (node.children[idx] == null) { return -1; } node = node.children[idx]; if (node.ref != -1) { return node.ref; } } return -1; } } class Solution { public String replaceWords(List<String> dictionary, String sentence) { Trie trie = new Trie(); for (int i = 0; i < dictionary.size(); ++i) { trie.insert(dictionary.get(i), i); } List<String> ans = new ArrayList<>(); for (String w : sentence.split("\\s")) { int idx = trie.search(w); ans.add(idx == -1 ? w : dictionary.get(idx)); } return String.join(" ", ans); } } 
  • class Trie { private: Trie* children[26]; int ref; public: Trie() : ref(-1) { memset(children, 0, sizeof(children)); } void insert(const string& w, int i) { Trie* node = this; for (auto& c : w) { int idx = c - 'a'; if (!node->children[idx]) { node->children[idx] = new Trie(); } node = node->children[idx]; } node->ref = i; } int search(const string& w) { Trie* node = this; for (auto& c : w) { int idx = c - 'a'; if (!node->children[idx]) { return -1; } node = node->children[idx]; if (node->ref != -1) { return node->ref; } } return -1; } }; class Solution { public: string replaceWords(vector<string>& dictionary, string sentence) { Trie* trie = new Trie(); for (int i = 0; i < dictionary.size(); ++i) { trie->insert(dictionary[i], i); } stringstream ss(sentence); string w; string ans; while (ss >> w) { int idx = trie->search(w); ans += (idx == -1 ? w : dictionary[idx]) + " "; } ans.pop_back(); return ans; } }; 
  • class Trie: def __init__(self): self.children: List[Trie | None] = [None] * 26 self.ref: int = -1 def insert(self, w: str, i: int): node = self for c in w: idx = ord(c) - ord("a") if node.children[idx] is None: node.children[idx] = Trie() node = node.children[idx] node.ref = i def search(self, w: str) -> int: node = self for c in w: idx = ord(c) - ord("a") if node.children[idx] is None: return -1 node = node.children[idx] if node.ref != -1: return node.ref return -1 class Solution: def replaceWords(self, dictionary: List[str], sentence: str) -> str: trie = Trie() for i, w in enumerate(dictionary): trie.insert(w, i) ans = [] for w in sentence.split(): idx = trie.search(w) ans.append(dictionary[idx] if idx != -1 else w) return " ".join(ans) 
  • type Trie struct { children [26]*Trie ref int } func newTrie() *Trie { return &Trie{ref: -1} } func (this *Trie) insert(w string, i int) { node := this for _, c := range w { idx := c - 'a' if node.children[idx] == nil { node.children[idx] = newTrie() } node = node.children[idx] } node.ref = i } func (this *Trie) search(w string) int { node := this for _, c := range w { idx := c - 'a' if node.children[idx] == nil { return -1 } node = node.children[idx] if node.ref != -1 { return node.ref } } return -1 } func replaceWords(dictionary []string, sentence string) string { trie := newTrie() for i, w := range dictionary { trie.insert(w, i) } ans := strings.Builder{} for _, w := range strings.Split(sentence, " ") { if idx := trie.search(w); idx != -1 { ans.WriteString(dictionary[idx]) } else { ans.WriteString(w) } ans.WriteByte(' ') } return ans.String()[:ans.Len()-1] } 
  • class Trie { private children: Trie[]; private ref: number; constructor() { this.children = new Array<Trie>(26); this.ref = -1; } public insert(w: string, i: number) { let node: Trie = this; for (const c of w) { const idx = c.charCodeAt(0) - 97; if (!node.children[idx]) { node.children[idx] = new Trie(); } node = node.children[idx]; } node.ref = i; } public search(w: string): number { let node: Trie = this; for (const c of w) { const idx = c.charCodeAt(0) - 97; if (!node.children[idx]) { return -1; } node = node.children[idx]; if (node.ref !== -1) { return node.ref; } } return -1; } } function replaceWords(dictionary: string[], sentence: string): string { const trie = new Trie(); for (let i = 0; i < dictionary.length; i++) { trie.insert(dictionary[i], i); } return sentence .split(' ') .map(w => { const idx = trie.search(w); return idx !== -1 ? dictionary[idx] : w; }) .join(' '); }

All Problems

All Solutions