648. Replace Words
Medium
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 derivative. For example, when the root "help"
is followed by the word "ful"
, we can form a derivative "helpful"
.
Given a dictionary
consisting of many roots and a sentence
consisting of words separated by spaces, replace all the derivatives in the sentence with the root forming it. If a derivative 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.
Solution:
class Solution { private $root; public function __construct() { $this->root = new TrieNode(); } /** * @param String[] $dictionary * @param String $sentence * @return String */ function replaceWords($dictionary, $sentence) { foreach ($dictionary as $word) { $this->insert($word); } $ans = ''; $iss = explode(' ', $sentence); foreach ($iss as $s) { $ans .= $this->search($s) . ' '; } $ans = rtrim($ans); return $ans; } private function insert($word) { $node = $this->root; for ($i = 0; $i < strlen($word); $i++) { $c = $word[$i]; $index = ord($c) - ord('a'); if ($node->children[$index] == null) { $node->children[$index] = new TrieNode(); } $node = $node->children[$index]; } $node->word = $word; } private function search($word) { $node = $this->root; for ($i = 0; $i < strlen($word); $i++) { $c = $word[$i]; if ($node->word != null) { return $node->word; } $index = ord($c) - ord('a'); if ($node->children[$index] == null) { return $word; } $node = $node->children[$index]; } return $word; }
} class TrieNode { public $children; public $word; public function __construct() { $this->children = array_fill(0, 26, null); $this->word = null; }
}
Contact Links
Discover more from Coursity
Subscribe to get the latest posts sent to your email.