Category Trie

LeetCode 211. Design Add and Search Words Data Structure

Arunima Mandal Leave a comment

Problem Link: https://leetcode.com/problems/design-add-and-search-words-data-structure/description/

Note: This problem involves an amazing application of Trie. The “.” in the problem statement gives a twist to the problem.

Code:

class WordDictionary {
public:
    struct TrieNode
    {
        TrieNode *child[26]={};
        bool w=0;
    };
    TrieNode *root=new TrieNode();
    WordDictionary() {
        
    }
    
    void addWord(string word) {
        TrieNode *it=root;
        for(int i=0; i<word.size(); i++)
        {
            int ind=word[i]-'a';
            if(!it->child[ind]) it->child[ind]=new TrieNode();
            it=it->child[ind];
        }
        it->w=1;
    }
    bool search(string word)
    {
        return search(root, word);
    }
    
    bool search(TrieNode *it, string word) {
        for(int i=0; i<word.size() && it; i++)
        {
            if(word[i]!='.')
            {
                int ind=word[i]-'a';
                if(!it->child[ind]) return false;
                it=it->child[ind];   
            }
            else
            {
                string s=word.substr(i+1);
                TrieNode *tmp=it;
                for(int j=0; j<26; j++)
                {
                    it=tmp->child[j];
                    if(search(it, s)) return true;
                }
            }
        }
        return it && it->w; //covers the case when the it is null, and that happens only when going from . to any other character which doesn't exist.
    }
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary* obj = new WordDictionary();
 * obj->addWord(word);
 * bool param_2 = obj->search(word);
 */

SPOJ – PHONELST – Phone List

Arunima Mandal Leave a comment

Problem Link: https://www.spoj.com/problems/PHONELST/


Solution: This is a pretty great problem regarding applying Trie in the case of a numerical string. If your code is not executing, please take a good look at whether you are taking the index as s[i]-‘0’ instead of s[i]-‘a’. Since in most cases, the strings consist of alphabets, so in most cases in the Trie code template, we can write the index code as s[i]-‘a’ habitually.

Here the main trick is to sort the vector containing strings before inserting those into the Trie, to make sure we are marking the smaller words first. Otherwise, we will miss the smaller words, and that way the long words with the same prefix equal to the smaller words will go undetected.

Code:

#include <bits/stdc++.h>

using namespace std;

struct TrieNode
{
    TrieNode *child[10]={};
    bool word=0;
};

bool insert(TrieNode *root, string s)
{
    TrieNode *it=root;
    for(int i=0; i<s.size(); i++)
    {
        int ind=s[i]-'0';
        if(it->word==1) return 0;
        if(!it->child[ind]) it->child[ind]= new TrieNode();
        it=it->child[ind];
    }
    it->word=1;
    return 1;
}

int main()
{
    int t,n;
    cin>>t;
    for(int z=0; z<t; z++)
    {
        int n;
        cin>>n;
        vector<string> v;
        string s;
        for(int i=0; i<n; i++)
        {
            cin>>s;
            v.push_back(s);
        }
        sort(v.begin(), v.end());

        TrieNode *root=new TrieNode();
        bool is_consistent=1;
        for(int i=0; i<n && is_consistent; i++)
        {
            is_consistent=insert(root, v[i]);
        }

        if(is_consistent) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

SPOJ – ADAINDEX – Ada and Indexing

Arunima Mandal Leave a comment

Problem Link: https://www.spoj.com/problems/ADAINDEX/

Note: The idea behind the problem is pretty simple. Just keep a count variable in each node while building the Trie, so that each node keeps track of its count in how many words it has been repeated.

Solution:

#include <bits/stdc++.h>

using namespace std;

struct TrieNode
{
    TrieNode *child[26]={};
    int cnt=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->cnt++;
    }
}

int search(TrieNode *root, string s)
{
    TrieNode *it=root;
    for(int i=0; i<s.size(); i++)
    {
        int ind=s[i]-'a';
        if(!it->child[ind]) return 0;
        it=it->child[ind];
    }
    return it->cnt;
}

int main()
{
    int n,q;
    cin>>n>>q;
    TrieNode *root=new TrieNode();
    for(int i=0; i<n; i++)
    {
        string s;
        cin>>s;
        insert(root, s);
    }

    for(int i=0; i<q; i++)
    {
        string s;
        cin>>s;
        cout<<search(root, s)<<endl;
    }
    return 0;
}

LeetCode 648. Replace Words

Arunima Mandal Leave a comment

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;
    }
};

Trie (Insert and Search)

Arunima Mandal Leave a comment

Note: I have understood the concept of Trie from the following link- https://www.geeksforgeeks.org/trie-insert-and-search/
I have just modified the code according to my understanding and tried to make the code concise.

Code:

#include <bits/stdc++.h>
using namespace std;

struct TrieNode
{
	TrieNode *child[26]={}; //if string contains alphabets only
	bool word=0;
};

void insert(struct TrieNode *root, string key)
{
	TrieNode *it = root;
	for (int i = 0; i < key.size(); i++)
	{
		int index = key[i] - 'a';
		if (!it->child[index]) it->child[index] = new TrieNode();
		it = it->child[index];
	}
	it->word = 1;
}

bool search(struct TrieNode *root, string key)
{
	TrieNode *it = root;
	for (int i = 0; i < key.size(); i++)
	{
		int index = key[i] - 'a';
		if (!it->child[index]) return false;
		it = it->child[index];
	}
	return (it->word);
}

// Driver
int main()
{
	// Input keys (use only 'a' through 'z' and lower case)
	vector<string> keys={"the", "a", "there", "answer", "any", "by", "bye", "their" };

	TrieNode *root = new TrieNode();

	// Construct trie
	for (int i = 0; i < keys.size(); i++)
		insert(root, keys[i]);

	// Search for different keys
	char output[][32] = {"Not present in trie", "Present in trie"};

	// Search for different keys
	cout<<"the"<<" --- "<<output[search(root, "the")]<<endl;
	cout<<"these"<<" --- "<<output[search(root, "these")]<<endl;
	cout<<"their"<<" --- "<<output[search(root, "their")]<<endl;
	cout<<"thaw"<<" --- "<<output[search(root, "thaw")]<<endl;
	return 0;
}