Interview Questions/Coding/Memo Root Compression

Memo Root Compression

Preview mode. Log in to edit, run, submit, and save progress.

Hard

Memo Root Compression

A policy memo contains words that may be shortened by an approved root dictionary. If a memo word begins with one or more approved roots, it must be replaced by the shortest approved root that matches the beginning of that word. Words that do not begin with any approved root stay exactly as they are. The original word order must be preserved, and the returned memo is formed by joining the transformed words with single spaces. Input Format: You are given an array roots and an array words. Output Format: Return the compressed memo text as a single string.

Examples

Example 1

Input:

roots = ["cat", "bat", "rat"]
words = ["the", "cattle", "was", "rattled", "by", "battery"]

Output:

the cat was rat by bat

Explanation: cattle -> cat, rattled -> rat, battery -> bat. After applying these replacements in order, the sentence becomes "the cat was rat by bat".

Approach hint

The shortest root is found naturally if the trie walk stops at the first terminal node.

Common mistake

Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.

solution.cpp