Spell Checker using Trie | Java 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
import java . io . * ; class TrieNode { TrieNode Trie [ ] ; boolean isEnd ; public TrieNode ( ) { Trie = new TrieNode [ 256 ] ; for ( int i = 0 ; i < 256 ; i ++ ) { Trie [ i ] = null ; } isEnd = false ; } } class GFG { static void InsertTrie ( TrieNode root , String s ) { TrieNode temp = root ; for ( int i = 0 ; i < s . length ( ) ; i ++ ) { if ( temp . Trie [ s . charAt ( i ) ] == null ) { temp . Trie [ s . charAt ( i ) ] = new TrieNode ( ) ; } temp = temp . Trie [ s . charAt ( i ) ] ; } temp . isEnd = true ; } static void printSuggestions ( TrieNode root , String res ) { if ( root . isEnd == true ) { System . out . print ( res + " ▁ " ) ; } for ( int i = 0 ; i < 256 ; i ++ ) { if ( root . Trie [ i ] != null ) { res += ( char ) i ; printSuggestions ( root . Trie [ i ] , res ) ; res = res . substring ( 0 , res . length ( ) - 2 ) ; } } } static boolean checkPresent ( TrieNode root , String key ) { for ( int i = 0 ; i < key . length ( ) ; i ++ ) { if ( root . Trie [ key . charAt ( i ) ] == null ) { printSuggestions ( root , key . substring ( 0 , i ) ) ; return false ; } root = root . Trie [ key . charAt ( i ) ] ; } if ( root . isEnd == true ) { return true ; } printSuggestions ( root , key ) ; return false ; } public static void main ( String [ ] args ) { String str [ ] = { " gee " , " geeks " , " ape " , " apple " , " geeksforgeeks " } ; String key = " geek " ; TrieNode root = new TrieNode ( ) ; for ( int i = 0 ; i < str . length ; i ++ ) { InsertTrie ( root , str [ i ] ) ; } if ( checkPresent ( root , key ) ) { System . out . println ( " YES " ) ; } } }