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:
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
