Prefix Based Word Replacement

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L5
Asked in
JPMorgan Chase

Problem

Given a list of root words and a whitespace-separated sentence, for each word in the sentence, if any root is a prefix of it, replace the word with the shortest such root. Return the transformed sentence with the same whitespace separations.

Every word trimmed to its root.

Example 1

Input:

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

Output:

"the cat was rat by the bat"

Example 2

Input:

roots = ["a","b","c"], sentence = "aadsfasf absbd cadsfabd"

Output:

"a a c"

Worked solution and explanation

Why this problem exists in real interviews

Replacing words by their root prefix tests string matching and whether you can optimize the lookup using a set or trie rather than brute-force scanning all roots for each word.

Break down the requirements

Step 1: Build a set of roots for O(1) membership testing

Convert the root list to a set.

Step 2: For each word, find the shortest matching root prefix

Check prefixes of increasing length. The first match in the root set is the shortest root.

Step 3: Replace the word with the root or keep it unchanged

If a root prefix is found, use it. Otherwise, keep the original word.

The solution

Prefix scanning with root set lookup
def replace_words(roots, sentence):
    root_set = set(roots)
    words = sentence.split()
    result_words = []
    for word in words:
        replacement = word
        for end in range(1, len(word) + 1):
            prefix = word[:end]
            if prefix in root_set:
                replacement = prefix
                break
        result_words.append(replacement)
    result = ' '.join(result_words)
    return result

Common follow-up questions