DICT - Search in the dictionary! - SPOJ Solution C++ ~ CodingWithArt

➤ Problem Link : DICT

👉 Hint : Use Trie Data Structure

✅ C++ Solution :

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

struct TrieNode
{
	struct TrieNode *children[26];
	bool isEndOfWord;
};

typedef struct TrieNode TNODE;

TNODE *CreateNode()
{
	TNODE *newNode=(TNODE *)malloc(sizeof(TNODE));
	for(int i=0;i<26;i++)
		newNode->children[i]=NULL;
	newNode->isEndOfWord=0;
	return newNode;
}

void insert(TNODE *root,string s)
{
	TNODE *current=root;
	for(int i=0;i<s.length();i++)
	{
		if(current->children[s[i]-'a']==NULL)
		{
			TNODE *newNode=CreateNode();
			current->children[s[i]-'a']=newNode;
		}
		current=current->children[s[i]-'a'];
	}
	current->isEndOfWord=1;
}


void PrintArr(char arr[],int n)
{
	for(int i=0;i<=n;i++)
		cout<<arr[i];
	cout<<"\n";
}

void printDict(TNODE *root,int ind,char arr[])
{
	if(root->isEndOfWord)
		PrintArr(arr,ind);
	for(int i=0;i<26;i++)
	{
		if(root->children[i])
		{
			arr[ind+1]=i+'a';
			printDict(root->children[i],ind+1,arr);
		}
	}


}

void Search(TNODE *root,string s)
{
	TNODE *current=root;
	char arr[21];
	int i,f=0,cnt=0;
	for(i=0;i<s.length();i++)
	{
		arr[i]=s[i];
		if(current->children[s[i]-'a']==NULL)
		{
			f=1;
			break;
		}
		current=current->children[s[i]-'a'];
	}
	i--;
	if(f!=1)
	{
		for(int j=0;j<26;j++)
		{
			if(!current->children[j])
				cnt++;
		}
	}	
	if(f==1 || cnt==26)
	{
		cout<<"No match.\n";
		return;
	}
	for(int j=0;j<26;j++)
	{
    	if(current->children[j])
    	{
    		arr[i+1]=j+'a';
			printDict(current->children[j],i+1,arr);
    	}
    }	
	
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n,k;
	cin>>n;
	string s;
	TNODE *root=CreateNode();
	while(n--)
	{
		cin>>s;
		insert(root,s);
	}
	cin>>k;
	for(int i=1;i<=k;i++)
	{
		cin>>s;
		cout<<"Case #"<<i<<":\n";
		Search(root,s);
	}
}

Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.

😇Happy Learning!!

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.