Get started

Replace Words — Medium Problem & Solution

In English, a root followed by a suffix forms a longer word — for example help gives helpful.

  • 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.

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)

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue