algoadvance

Leetcode 648. Replace Words

Problem Statement

You are given a dictionary consisting of many roots and a sentence. You need to replace all the successors in the sentence with the root forming it. If a successor can be replaced by more than one root, replace it with the root with the shortest length.

Example:

  1. Input:
    • dictionary = ["cat","bat","rat"]
    • sentence = "the cattle was rattled by the battery"
    • Output: "the cat was rat by the bat"
  2. Input:
    • dictionary = ["a", "b", "c"]
    • sentence = "aadsfasf absbs bbab cadsfafs"
    • Output: "a a b c"
  3. 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"

Clarifying Questions

  1. What are the constraints on the lengths of the dictionary and sentence?
  2. Can the dictionary contain duplicate roots?
  3. How should we handle punctuation and capitalization?

Strategy

  1. Trie Construction:
    • A Trie (Prefix Tree) is an efficient structure to store the dictionary roots and quickly match prefixes of words in the sentence.
  2. Replacing Process:
    • For each word in the sentence, attempt to find the shortest root from the dictionary using the Trie.
    • Replace with the root if a match is found; otherwise, keep the original word.
  3. Implementation Steps:
    • Construct a Trie with all roots from the dictionary.
    • Split the sentence into words.
    • For each word in the sentence, find its root using the Trie.
    • Replace the word with its root if found, otherwise leave it as is.
    • Join the words back into a sentence.

Code

import java.util.*;

class Solution {
    // Trie Node
    class TrieNode {
        Map<Character, TrieNode> children;
        boolean isEndOfWord;
        
        public TrieNode() {
            children = new HashMap<>();
            isEndOfWord = false;
        }
    }
    
    private TrieNode root;
    
    // Initialize the Trie
    public Solution() {
        root = new TrieNode();
    }
    
    // Insert a word into the Trie
    private void insert(String word) {
        TrieNode current = root;
        for (char ch : word.toCharArray()) {
            current.children.putIfAbsent(ch, new TrieNode());
            current = current.children.get(ch);
        }
        current.isEndOfWord = true;
    }
    
    // Search for the shortest root in the Trie
    private String searchRoot(String word) {
        TrieNode current = root;
        StringBuilder sb = new StringBuilder();
        for (char ch : word.toCharArray()) {
            if (!current.children.containsKey(ch)) break;
            sb.append(ch);
            current = current.children.get(ch);
            if (current.isEndOfWord) return sb.toString();
        }
        return word;
    }
    
    public String replaceWords(List<String> dictionary, String sentence) {
        // Insert all dictionary roots into the Trie
        for (String root : dictionary) {
            insert(root);
        }
        
        // Split the sentence into words
        String[] words = sentence.split(" ");

        // Build the replaced sentence
        StringBuilder replacedSentence = new StringBuilder();
        for (String word : words) {
            if (replacedSentence.length() > 0) replacedSentence.append(" ");
            replacedSentence.append(searchRoot(word));
        }
        
        return replacedSentence.toString();
    }
}

Time Complexity

  1. Trie Construction: O(M * N), where M is the number of words in the dictionary and N is the average length of each word.
  2. Replacement Process: O(L), where L is the total number of characters in the sentence.
  3. Overall: The combined time complexity is O(M * N + L), which is efficient for typical use cases of this problem.

This implementation allows for efficient querying and replacement of words in the sentence using the provided dictionary.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI