Spell Checker using Trie | C ++ program to implement the above approach ; Structure of a Trie node ; Store address of a character ; Check if the character is last character of a string or not ; Constructor function ; Function to insert a string into Trie ; Traverse the string , s ; Initialize a node ; Update temp ; Mark the last character of the string to true ; Function to print suggestions of the string ; If current character is the last character of a string ; Iterate over all possible characters of the string ; If current character present in the Trie ; Insert current character into Trie ; Function to check if the string is present in Trie or not ; Traverse the string ; If current character not present in the Trie ; Update root ; Driver Code ; Given array of strings ; Initialize a Trie ; Insert strings to trie
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct TrieNode { TrieNode * Trie [ 256 ] ; bool isEnd ; TrieNode ( ) { for ( int i = 0 ; i < 256 ; i ++ ) { Trie [ i ] = NULL ; } isEnd = false ; } } ; void InsertTrie ( TrieNode * root , string s ) { TrieNode * temp = root ; for ( int i = 0 ; i < s . length ( ) ; i ++ ) { if ( temp -> Trie [ s [ i ] ] == NULL ) { temp -> Trie [ s [ i ] ] = new TrieNode ( ) ; } temp = temp -> Trie [ s [ i ] ] ; } temp -> isEnd = true ; } void printSuggestions ( TrieNode * root , string res ) { if ( root -> isEnd == true ) { cout << res << " ▁ " ; } for ( int i = 0 ; i < 256 ; i ++ ) { if ( root -> Trie [ i ] != NULL ) { res . push_back ( i ) ; printSuggestions ( root -> Trie [ i ] , res ) ; res . pop_back ( ) ; } } } bool checkPresent ( TrieNode * root , string key ) { for ( int i = 0 ; i < key . length ( ) ; i ++ ) { if ( root -> Trie [ key [ i ] ] == NULL ) { printSuggestions ( root , key . substr ( 0 , i ) ) ; return false ; } root = root -> Trie [ key [ i ] ] ; } if ( root -> isEnd == true ) { return true ; } printSuggestions ( root , key ) ; return false ; } int main ( ) { vector < string > str = { " gee " , " geeks " , " ape " , " apple " , " geeksforgeeks " } ; string key = " geek " ; TrieNode * root = new TrieNode ( ) ; for ( int i = 0 ; i < str . size ( ) ; i ++ ) { InsertTrie ( root , str [ i ] ) ; } if ( checkPresent ( root , key ) ) { cout << " YES " ; } return 0 ; }