q1trie

PHOTO EMBED

Wed Sep 28 2022 20:42:31 GMT+0000 (Coordinated Universal Time)

Saved by @Lokesh8126 #c++ 

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

class TrieNode
{
public:
	char data;
	TrieNode ** children;
	bool isEndOfString = false;
	TrieNode(char data)
	{
		this->data = data;
		children = new TrieNode*[26];
		for (int i = 0; i < 26; ++i)
		{
			children[i] = NULL;
		}
		isEndOfString = false;
	}
};


class Trie
{
	TrieNode *root;
public:
	Trie()
	{
		root = new TrieNode ('\0');
	}
private:
	void insertWord(TrieNode *root , string word)
	{
		//base case
		if (word.size() == 0)
		{
			root->isEndOfString = true;
			return;
		}

		//small calculation
		int index = word[0] - 'a'; //for 0th letter
		// a-0 b-1 c-2 d-3 e-4 f-5 g-6---y-24 z-25
		//now check at that particular index
		TrieNode * child;
		if (root->children[index] == NULL)
		{
			//make new node and put its address childern ptr
			child = new TrieNode(word[0]);
			root-> children[index] = child;
		}
		else
		{
			child = root->children[index];
			//child will take address  for recursive call
		}
		//recursion from index one
		insertWord(child , word.substr(1));
	}

public:
	void insertWord(string word)
	{
		return insertWord(this->root , word);
	}

private:
	bool search(TrieNode*root , string word)
	{
		if (word.size() == 0)
		{
			return 	root->isEndOfString;
		}
		TrieNode *child;
		int index = word[0] - 'a';
		if ( root->children[index] != NULL)
		{
			child = root->children[index];
		}
		else
			return false;

		return search(child , word.substr(1));

	}

public:
	bool search(string word)
	{
		return search(this->root, word);
	}

	void display(TrieNode* node , string word, vector<string> & v)
	{
		if (node->isEndOfString == true)
		{
			// cout << word << endl;
			v.push_back(word);
		}

		TrieNode * child;
		for (int i = 0; i < 26; ++i)
		{
			if (node->children[i] != NULL )
			{
				child = node->children[i];
				display(child , word + node->children[i]->data, v);
			}
		}
	}

	void display()
	{
		string word = "";
		vector <string> v;
		display(root, word , v);
	}

private:
	TrieNode* autoComplete(TrieNode*node , string word)
	{
		if ( word.length() == 0)
			return node;
		TrieNode *child;
		int index = word[0] - 'a';
		if ( node->children[index] != NULL)
		{
			child = node->children[index];
		}
		else
			return NULL;
		TrieNode * n =  autoComplete(child , word.substr(1));
		return n;
	}

public:
	void autoComplete(string word)
	{
		string a = word;
		TrieNode*node =  autoComplete(root, word);
		// cout << node->data << endl;
		if (node)
		{

			vector<string>v;
			display(node , word, v );
			cout << v.size() << endl;
			for (int i = 0; i < v.size(); ++i)
			{
				cout << v[i] << endl;
			}
		}
		else
		{
			cout << "\n Not a valid word to autoComplete:" << endl;
		}
	}

	int  distance(string str1 , string str2)
	{

		int cost = 0;

		int m = str1.length();
		int n = str2.length();

		int lev[m + 1][n + 1];
		for (int i = 0; i <= m; ++i)
		{
			for (int j = 0; j <= n; ++j)
			{
				lev[i][j] = 0;
			}
		}

		for (int i = 0; i <= m; i++)
			lev[i][0] =  i;

		for (int j = 0; j <= n; j++)
			lev[0][j] = j;

		for (int j = 1; j <= n; ++j)
		{
			for (int i = 1; i <= m; ++i)
			{
				if (str1[i] == str2[j])
					cost = 0 ;
				else
					cost = 1;
				lev[i][j] =  min(lev[i - 1][j - 1] + cost,  min(1 + lev[i - 1][j], 1 + lev[i][j - 1]));

			}
		}

		return lev[m][n];
	}

	void edit_dis_word(TrieNode*node, string word , string lev_word , vector<string>&v)
	{
		if (node->isEndOfString == true)
		{
			int k = distance(word , lev_word);
			if (k <= 3)
				v.push_back(word);
		}

		TrieNode * child;
		for (int i = 0; i < 26; ++i)
		{
			if (node->children[i] != NULL )
			{
				child = node->children[i];
				edit_dis_word(child , word + node->children[i]->data, lev_word, v);
			}
		}
	}


	void autoCorrect(string lev_word)
	{

		vector<string>matching;
		//for storing the lev_distance owrd
		edit_dis_word(root , "" , lev_word, matching);
		cout << matching.size() << endl;

		for (int i = matching.size() - 1; i >= 0 ; i--)
		{
			cout << matching[i] << endl;
		}

	}
};


int main()
{
#ifdef ONLINE_JUDGE
	freeopen("input.txt", "r", stdin);
	freeopen("output.txt", "r", stdin);
#endif
	int num_words;
	int q;
	cin >> num_words >> q;
	Trie t;
	string word;
	while (num_words--)
	{
		cin >> word;
		t.insertWord(word);
	}

	int choice;
	while (q--)
	{
		cin >> choice;
		if (choice == 1) // spell check
		{
			cin >> word;
			cout << (t.search(word) ? "1\n" : "0\n");
		}
		else if (choice == 2) //auto complete
		{
			cin >> word;
			t.autoComplete(word);
		}
		else if (choice == 3)
		{
			cin >> word;
			t.autoCorrect(word);// autoCorrect
		}

	}

	// t.display();



	return 0;
}
content_copyCOPY