LeetCode 648. Replace Words

Arunima Mandal

Problem: https://leetcode.com/problems/replace-words/description/

Solution:

The intuition to the problem is pretty simple.

  • Build the trie data structure by inserting all the words from the dictionary.
  • Go through the sentence, take each word(separated by space), and search in the trie for the root in that word.
    1. If the root is found (trie naturally ensures the shortest length root), then stop and return the index so that we can take that as the substring.
    2. Otherwise, we have to take the entire word, so return the total length of the word we were considering.

Complexity:

  • Time complexity:

O(n) where n is the length of the sentence.

  • Space complexity:

O(n) where n is the size of our trie data structure.

Code:

class Solution {
public:
    struct TrieNode{
        TrieNode *child[26]={};
        bool end=0;
    };
    void insert(TrieNode *root, string s)
    {
        TrieNode *it=root;
        for(int i=0; i<s.size(); i++)
        {
            int ind=s[i]-'a';
            if(!it->child[ind]) it->child[ind]=new TrieNode();
            it=it->child[ind];
        }
        it->end=1;
    }
    int search(TrieNode *root, string s)
    {
        TrieNode *it=root;
        bool found=0;
        for(int i=0; i<s.size(); i++)
        {
            int ind=s[i]-'a';
            if(!it->child[ind]) break; //didn't find any root
            it=it->child[ind];
            if(it->end==1) return i+1;
        }
        return s.size(); 
    }
    string replaceWords(vector<string>& dictionary, string sentence) {
        TrieNode *root=new TrieNode();
        for(int i=0; i<dictionary.size(); i++)
        {
            insert(root, dictionary[i]);
        }
        string ans="",s="";
        for(int i=0; i<sentence.size(); i++)
        {
            if(sentence[i]==' ') 
            {
                int x=search(root, s);
                ans+=s.substr(0,x);
                ans+=" ";
                s.clear();
            }
            else s+=sentence[i];
        }
        int x=search(root, s); //for last word of the sentence
        ans+=s.substr(0,x);
        return ans;
    }
};

Leave a comment