algoadvance

Leetcode 648. Replace Words

Problem Statement

Given a dictionary of words, find all occurrences of the roots in the sentence and replace them with the root itself. If a word has multiple roots, replace it with the shortest one.

Example:

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

Notes:

  1. The input will be in lowercase letters.
  2. The output should be a lowercase sentence.

Clarifying Questions

  1. What should be the behavior for words in the sentence that have no root in the dictionary?
    • They should remain unchanged in the sentence.
  2. Can we assume the dictionary and the sentence are both non-empty?
    • Yes, for simplification we can assume both are non-empty.
  3. Are all characters in the dictionary and the sentence lowercase?
    • Yes, as specified in the problem description.

Strategy

  1. Trie Data Structure: Use a Trie (prefix tree) to store the dictionary words. This allows for efficient prefix searching.
  2. Splitting the Sentence: Split the input sentence into words.
  3. Replace Words: For each word in the sentence, find the shortest prefix in the Trie and replace the word with this prefix. If no prefix is found, keep the word unchanged.
  4. Reconstruct Sentence: Join the words back into a single string.

Code

Here is the C++ implementation for the described problem:

#include <iostream>
#include <vector>
#include <sstream>
#include <unordered_map>

using namespace std;

class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    string word;
    TrieNode() : word("") {}
};

class Trie {
private:
    TrieNode* root;
    
public:
    Trie() {
        root = new TrieNode();
    }
    
    void insert(string word) {
        TrieNode* node = root;
        for(char ch : word) {
            if(!node->children.count(ch)) {
                node->children[ch] = new TrieNode();
            }
            node = node->children[ch];
        }
        node->word = word;
    }
    
    string searchPrefix(string word) {
        TrieNode* node = root;
        for(char ch : word) {
            if(node->children.count(ch)) {
                node = node->children[ch];
                if(!node->word.empty()) { // If a word is found in the trie
                    return node->word;
                }
            } else {
                break;
            }
        }
        return word; // Return original word if no prefix found
    }
};

class Solution {
public:
    string replaceWords(vector<string>& dictionary, string sentence) {
        Trie trie;
        for(string root : dictionary) {
            trie.insert(root);
        }
        
        stringstream ss(sentence);
        string word;
        string result = "";
        
        while(ss >> word) {
            if(!result.empty()) {
                result += " ";
            }
            result += trie.searchPrefix(word);
        }
        
        return result;
    }
};

// Helper function to print the solution
int main() {
    vector<string> dictionary = {"cat", "bat", "rat"};
    string sentence = "the cattle was rattled by the battery";
    
    Solution solution;
    string replacedSentence = solution.replaceWords(dictionary, sentence);
    
    cout << replacedSentence << endl; // Output: "the cat was rat by the bat"
    
    return 0;
}

Time Complexity

  1. Trie Construction: O(D * L) where D is the number of dictionary words and L is the maximum length of a dictionary word.
  2. Search Prefix: For a sentence of length N and each word of maximum length L, the prefix search operation will be O(N * L).

Overall, the time complexity is O(D * L + N * L).

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