Replace Words

medium trie string

Problem

Replace every word in a sentence with its shortest dictionary root prefix when one exists.

Inputdict=['cat','bat','rat'] sent='the cattle was rattled by the battery'

Output'the cat was rat by the bat'

Each word gets shortened to its prefix root if any.

input

def replace_words(roots, sentence):
    trie = {}
    for r in roots:
        node = trie
        for c in r: node = node.setdefault(c, {})
        node['$'] = r
    def shorten(w):
        node = trie
        for c in w:
            if c not in node or '$' in node: break
            node = node[c]
        return node.get('$', w)
    return ' '.join(shorten(w) for w in sentence.split())

function replaceWords(roots, sentence) {
  const trie = {};
  for (const r of roots) {
    let node = trie;
    for (const c of r) node = node[c] ||= {};
    node.$ = r;
  }
  const shorten = w => {
    let node = trie;
    for (const c of w) {
      if (!node[c] || node.$) break;
      node = node[c];
    }
    return node.$ || w;
  };
  return sentence.split(' ').map(shorten).join(' ');
}

String replaceWords(List roots, String sentence) {
    Map trie = new HashMap<>();
    for (String r : roots) {
        Map n = trie;
        for (char c : r.toCharArray()) n = (Map) n.computeIfAbsent("" + c, k -> new HashMap<>());
        n.put("$", r);
    }
    StringBuilder out = new StringBuilder();
    for (String w : sentence.split(" ")) {
        if (out.length() > 0) out.append(' ');
        Map n = trie;
        boolean done = false;
        for (char c : w.toCharArray()) {
            if (!n.containsKey("" + c) || n.containsKey("$")) break;
            n = (Map) n.get("" + c);
        }
        out.append(n.containsKey("$") ? n.get("$") : w);
    }
    return out.toString();
}

string replaceWords(vector& roots, string sentence) {
    struct Node { unordered_map ch; string word; };
    Node* trie = new Node;
    for (auto& r : roots) {
        Node* n = trie;
        for (char c : r) { if (!n->ch[c]) n->ch[c] = new Node; n = n->ch[c]; }
        n->word = r;
    }
    stringstream ss(sentence); string w, out;
    while (ss >> w) {
        Node* n = trie;
        for (char c : w) { if (!n->ch.count(c) || !n->word.empty()) break; n = n->ch[c]; }
        if (!out.empty()) out += ' ';
        out += n->word.empty() ? w : n->word;
    }
    return out;
}

Explanation

We want to swap each word in a sentence for the shortest dictionary root that starts it. Instead of testing every word against every root, we store all the roots in a trie (a tree of letters) so we can match a prefix really fast.

Building the trie is one loop: for each root we walk letter by letter with node.setdefault(c, {}), then mark the end with node['$'] = r so we remember which root finished here.

To shorten a word we walk the trie following its letters. The moment we land on a node that has the end marker '$', we stop early — that is the shortest root. If we ever hit a letter that is not in the trie, there is no root, so we keep the original word.

Example: roots cat, bat, rat. For the word cattle we walk c → a → t, find '$' marking cat, and stop. So cattle becomes cat.

Finally we join the shortened words back with spaces. Because each lookup only follows a word's own letters, the whole pass is fast.

Time: O(N + S) Space: O(N)