Replace Words

Medium
655.

Replace Words

Replace Words is a medium coding problem on strings, hash table and trie, asked in Amazon, Google and Adobe interviews.

In English, a root followed by a suffix forms a longer word — for example help gives helpful. You are given a dictionary of roots and a sentence of space-separated words.

Replace every word that has a root as a prefix with that root. When several roots match, use the shortest one. Words with no matching root are left alone.

Return the rewritten sentence.

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 = ["code","kai"], sentence = "codekairo kairo rocks"
Output
code kai rocks
Explanation
"codekairo" starts with the root "code"; "kairo" starts with "kai"; "rocks" matches nothing.

Example 3

Input
dictionary = ["a","aa","aaa"], sentence = "aaaa bedded"
Output
a bedded
Explanation
The shortest matching root wins.

Constraints

  • 1 <= dictionary.length <= 1000
  • 1 <= dictionary[i].length <= 100
  • 1 <= sentence words <= 1000
  • sentence holds lowercase words separated by single spaces.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} dictionary
 * @param {string} sentence
 * @return {string}
 */
var replaceWords = function(dictionary, sentence) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Replace Words — Solution in Python, Java & C++

Replace Words solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on strings and hash table.

Replace Words is a medium coding problem on strings, hash table and trie, asked in Amazon, Google and Adobe interviews.

  • Difficulty: Medium
  • Topics: Strings, Hash Table, Trie
  • Asked at: Amazon, Google, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

In English, a root followed by a suffix forms a longer word — for example help gives helpful. You are given a dictionary of roots and a sentence of space-separated words.

Replace every word that has a root as a prefix with that root. When several roots match, use the shortest one. Words with no matching root are left alone.

Return the rewritten sentence.

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 = ["code","kai"], sentence = "codekairo kairo rocks"
Output: code kai rocks
Explanation: "codekairo" starts with the root "code"; "kairo" starts with "kai"; "rocks" matches nothing.

Example 3

Input: dictionary = ["a","aa","aaa"], sentence = "aaaa bedded"
Output: a bedded
Explanation: The shortest matching root wins.

Constraints

  • 1 <= dictionary.length <= 1000
  • 1 <= dictionary[i].length <= 100
  • 1 <= sentence words <= 1000
  • sentence holds lowercase words separated by single spaces.

Hints for Replace Words

  1. Hint 1

    Put the roots in a set, then for each word try its prefixes from shortest to longest.

  2. Hint 2

    The first hit is by construction the shortest root — stop there.

  3. Hint 3

    A trie does the same job in one walk per word and is the intended structure at scale.

How to solve Replace Words

For each word, the shortest matching root is found by testing its prefixes in increasing length and stopping at the first hit. A hash set makes each test O(1); a trie makes the whole word one walk.

Approach

  1. Insert every root into a set.
  2. Split the sentence on spaces.
  3. For each word, test prefixes of length 1, 2, … and replace with the first one present in the set.
  4. Join the results back with single spaces.

Why it works

Scanning prefixes shortest-first means the first match is minimal by construction, which is exactly the tie-break the statement asks for. A trie walk reaches the same answer by stopping at the first node marked as a root.

Complexity

  • Time — O(total characters in the sentence × max root length) with a set; O(total characters) with a trie
  • Space — O(total dictionary characters)

Pitfalls

  • Testing prefixes longest-first gives the longest root, which is the wrong tie-break.
  • Joining with the wrong separator or dropping empty results changes the sentence — the split is on single spaces.

Reference solution

Python

from typing import List

def replaceWords(dictionary: List[str], sentence: str) -> str:
    roots = set(dictionary)
    out = []
    for w in sentence.split(" "):
        replaced = w
        for i in range(1, len(w) + 1):
            if w[:i] in roots:
                replaced = w[:i]
                break
        out.append(replaced)
    return " ".join(out)

Java

public static String replaceWords(String[] dictionary, String sentence) {
    Set<String> roots = new HashSet<>(Arrays.asList(dictionary));
    String[] words = sentence.split(" ");
    StringBuilder sb = new StringBuilder();
    for (int j = 0; j < words.length; j++) {
        String w = words[j];
        String replaced = w;
        for (int len = 1; len <= w.length(); len++) {
            String pre = w.substring(0, len);
            if (roots.contains(pre)) { replaced = pre; break; }
        }
        if (j > 0) sb.append(' ');
        sb.append(replaced);
    }
    return sb.toString();
}

C++

string replaceWords(vector<string>& dictionary, string sentence) {
    unordered_set<string> roots(dictionary.begin(), dictionary.end());
    string out, word;
    stringstream ss(sentence);
    bool first = true;
    while (ss >> word) {
        string replaced = word;
        for (size_t len = 1; len <= word.size(); len++) {
            string pre = word.substr(0, len);
            if (roots.count(pre)) { replaced = pre; break; }
        }
        if (!first) out += " ";
        out += replaced;
        first = false;
    }
    return out;
}

JavaScript

var replaceWords = function(dictionary, sentence) {
    var roots = {};
    for (var i = 0; i < dictionary.length; i++) roots[dictionary[i]] = true;
    var words = sentence.split(" ");
    var out = [];
    for (var j = 0; j < words.length; j++) {
        var w = words[j], replaced = w;
        for (var len = 1; len <= w.length; len++) {
            var pre = w.substr(0, len);
            if (roots[pre] === true) { replaced = pre; break; }
        }
        out.push(replaced);
    }
    return out.join(" ");
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets