304 North Cardinal St.
Dorchester Center, MA 02124

Replace Words LeetCode Solution

Problem – Replace Words

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.

Replace Words LeetCode Solution in Java

``````public String replaceWords(List<String> dict, String sentence) {
String[] tokens = sentence.split(" ");
TrieNode trie = buildTrie(dict);
return replaceWords(tokens, trie);
}

private String replaceWords(String[] tokens, TrieNode root) {
StringBuilder stringBuilder = new StringBuilder();
for (String token : tokens) {
stringBuilder.append(getShortestReplacement(token, root));
stringBuilder.append(" ");
}
return stringBuilder.substring(0, stringBuilder.length()-1);
}

private String getShortestReplacement(String token, final TrieNode root) {
TrieNode temp = root;
StringBuilder stringBuilder = new StringBuilder();
for (char c : token.toCharArray()) {
stringBuilder.append(c);
if (temp.children[c - 'a'] != null) {
if (temp.children[c - 'a'].isWord) {
return stringBuilder.toString();
}
temp = temp.children[c - 'a'];
} else {
}
}
}

private TrieNode buildTrie(List<String> dict) {
TrieNode root = new TrieNode(' ');
for (String word : dict) {
TrieNode temp = root;
for (char c : word.toCharArray()) {
if (temp.children[c - 'a'] == null) {
temp.children[c - 'a'] = new TrieNode(c);
}
temp = temp.children[c - 'a'];
}
temp.isWord = true;
}
return root;
}

public class TrieNode {
char val;
TrieNode[] children;
boolean isWord;

public TrieNode(char val) {
this.val = val;
this.children = new TrieNode[26];
this.isWord = false;
}
}
``````

Replace Words LeetCode Solution in Python

``````def replaceWords(self, roots, sentence):
_trie = lambda: collections.defaultdict(_trie)
trie = _trie()
END = True
for root in roots:
cur = trie
for letter in root:
cur = cur[letter]
cur[END] = root

def replace(word):
cur = trie
for letter in word:
if letter not in cur: break
cur = cur[letter]
if END in cur:
return cur[END]
return word

return " ".join(map(replace, sentence.split()))
``````

Replace Words LeetCode Solution in C++

``````class trie {
bool isRoot = false;
trie* l[26] = {};
public:
void insert(string& word, int ch, int sz) {
isRoot |= ch == sz;
if (!isRoot) { // stop at the shortest root.
if (l[word[ch] - 'a'] == nullptr) l[word[ch] - 'a'] = new trie();
l[word[ch] - 'a']->insert(word, ch + 1, sz);
}
}
int root(string& word, int st, int ch, int sz) {
if (st + ch == sz || word[st + ch] == ' ' || this->isRoot) return ch;
if (l[word[st + ch] - 'a'] == nullptr) { // root was not found
while (st + ch < sz && word[st + ch] != ' ') ++ch; // skipping the entire word
return ch;
}
return l[word[st + ch] - 'a']->root(word, st, ch + 1, sz);
}
};
string replaceWords(vector<string>& dict, string snt) {
trie t;
string res;
for (auto s : dict) t.insert(s, 0, s.size());
for (int i = 0; i < snt.size(); ) {
if (snt[i] == ' ') res += snt[i++];
auto chars = t.root(snt, i, 0, snt.size());
res += snt.substr(i, chars);
for (i += chars; i < snt.size() && snt[i] != ' '; ++i);
}
return res;
}
``````
Replace Words LeetCode Solution Review:

In our experience, we suggest you solve this Replace Words LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Replace Words LeetCode Solution

Find on LeetCode

Conclusion:

I hope this Replace Words LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions