Problem Description

In English, there exists a concept called root which can be combined with other words to form longer words called successors. To example, the root "an" combined with "other" forms the word "another".

Given a dictionary of roots and a sentence, replace all successor words in the sentence with they shortest matching root. If a successor has multiple possible roots, use the shortest one.

Examples

Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

Input: dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
Output: "a a b c"

Input: dictionary = ["a", "aa", "aaa", "aaaa"], sentence = "a aa a aaaa aaa aaa aaa aaaaaa bbb baba ababa"
Output: "a a a a a a a a bbb baba a"

Constraints

• 1 ≤ dictionary.length ≤ 1000
• 1 ≤ dictionary[i].length ≤ 100
• dictionary[i] consists of lowercase letters only
• 1 ≤ sentence.length ≤ 10^6
• sentence consists of lowercase letters and spaces only
• Number of words in senetnce: 1 to 1000
• Word length in sentence: 1 to 1000
• Words separated by single space
• No leading or trailing spaces in sentence

Solution Approach

This problem can be efficiently solved using a Trie data structure. The Trie stores all dictionary roots, enabling quick prefix matching for each word in the sentence.

Trie Implementation

type TrieNode struct {
    children [26]*TrieNode
    isEnd    bool
}

func CreateTrie() *TrieNode {
    return &TrieNode{
        children: [26]*TrieNode{},
        isEnd:    false,
    }
}

func (trie *TrieNode) AddWord(word string) {
    current := trie
    for _, char := range word {
        index := char - 'a'
        if current.children[index] == nil {
            current.children[index] = CreateTrie()
        }
        current = current.children[index]
    }
    current.isEnd = true
}

func (trie *TrieNode) FindShortestPrefix(word string) string {
    current := trie
    var prefix strings.Builder
    
    for _, char := range word {
        idx := char - 'a'
        if current.children[idx] == nil {
            return word
        }
        
        prefix.WriteRune(char)
        current = current.children[idx]
        
        if current.isEnd {
            return prefix.String()
        }
    }
    return word
}

Main Solution Function

func replaceWordsWithPrefix(roots []string, text string) string {
    trie := CreateTrie()
    
    for _, root := range roots {
        trie.AddWord(root)
    }
    
    words := strings.Fields(text)
    for i, word := range words {
        words[i] = trie.FindShortestPrefix(word)
    }
    
    return strings.Join(words, " ")
}

Algorithm Explanation

The solution builds a Trie containing all dictionary roots. For each word in the input sentence, it traverses the Trie character by character. If a complete root is found during traversal, that root replaces the original word. If no root matches, the original word remains unchanged.

The Trie structure ensures efficient prefix matching, making this solution optimal for the given constraints.