Replace Words

**Problem Statement:** Given the required input arguments, write an efficient algorithm to solve the **Replace Words** problem. Implement the required logic as specified by standard definitions for this classic algorithmic challenge. **Hint / Expected Approach:** Trie insert roots; for each word find shortest prefix **Edge Cases to Consider:** - (1) No roots match - (2) Root equals whole word - (3) Multiple matching roots

Examples

Example 1

Input: ["cat","bat","rat"], "the cattle was rattled by the battery"

Output: "the cat was rat by the bat"

Explanation: Classic

Example 2

Input: ["a","b","c"], "aadsfasf absbs bbab cadsfafs"

Output: "a a b c"

Explanation: Single-char roots

Example 3

Input: ["a","aa","aaa"], "aaaaaaaaaa"

Output: "a"

Explanation: Shortest root wins

Constraints

▪Input arguments are within valid ranges
▪Optimize for execution speed
▪Handle null/empty inputs gracefully

Watch Out For Edge Cases

▪No roots match
▪Root equals whole word
▪Multiple matching roots

Frequently Asked At

AmazonGoogleMicrosoftAdobe

Back to Arena

medium

Trie