BEST c++ solution with EASIEST explanation, TRIE explained
\n\nthe one obvious solution is adding the string into a set or may be unordered_set and for searching\nany string you can use regex  but the time complexity of
\n```\nthe one obvious solution is adding the string into a set or may be unordered_set and for searching\nany string you can use regex  but the time complexity of such kind of solution will be large and \nthis is not the recommended solution if asked in interview\nSo then, what should we do? We can use TRIE.\nWAIT WHAT !!! WHAT THE HECK IS TRIE IS?? I am a beginner. I dont understand what trie is!!!!\nWell your wait is over and today you will learn what trie is.\n\nWell TRIE is a fancy name of a data structure which contains an array of pointers pointing to nodes like \nitself. Well, this is a lame way of putting it. But this will do the job as of now.\nWhat i am saying is written in the below code:\nstruct Trie{\n        Trie *arr[26];  // an array of pointers pointing to the data type of Trie type\n        bool isend;\n        Trie(){    //constructor for initializing those pointers to NULL\n            for(int i =0;i<26;i++){\n                arr[i]=NULL;\n            }\n            isend=false;\n        }\n    };\n\t\nWell, does this remind you of sort of linked list data structure?? No?? Just a sec, it isnt exaclty the same\nbut it kinda resembles\n\nclass Node{--------------------------->struct Trie{\n\tint data;                                 bool isend;\n\tNode *next; ------------------------------>Trie *arr[26]; \n\t// the only diff is  in Node , we have 1 pointer and in trie we have an array of pointers.\n}\nwell as of now, you have understood the basic structure of TRIE, but how this is helping us to solve\nthe solution. Lets understand\n\nThis is the representation of a trie with 26 pointers (why 26? bcoz there are 26 alphabets dude!!)\n\n               Root\n\t\t\t      |\n----------------------------------------------------------------------------------------------------\na | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z\n----------------------------------------------------------------------------------------------------\n\nand now we want to store lets say "bud" in our trie. Initially all pointers are NULL and we will store\n" b u d" character by character.\n\nSo first we will store " b ". wo we will go to the pointer which is responsible for storing " b ".\nBut we have an array of pointers right, so how to access that index of the array which is pointing\nto " b "?? Simple dude !!!  Do --->  word[i]-\'a\'  so \'b\'-\'a\' and it will give 1. Please do not ask me \nhow this is possbile ?? ascii values pal !!!!!!! well i am not going to explain this to you :( !!\nSo we will go to the index 1 which logically says that i am b and we will create a node and will\nmake that pointer pointing to that new node. Just a sec, i hope you know that we need not to\nstore this "b" right? bcoz that task is already taken care by the index of our pointer of arrays.\n\nNow our trie looks like this now :\n                 Root\n\t\t\t      |\n----------------------------------------------------------------------------------------------------\na | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z\n----|------------------------------------------------------------------------------------------------\n    |\n    |\n   \\|/    this is our new node which is being pointed by b\n----------------------------------------------------------------------------------------------------\na | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z\n----------------------------------------------------------------------------------------------------\nSimilarly we can add " u ", so now our trie looks like this :\n===========================================================\n\n                 Root\n\t\t\t      |\n----------------------------------------------------------------------------------------------------\na | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z\n----|------------------------------------------------------------------------------------------------\n    |\n    |\n   \\|/    this is our new node which is being pointed by b\n----------------------------------------------------------------------------------------------------\na | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z\n--------------------------------------------------------------------------------|--------------------\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t|\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t|\n\t\t\t\t                                 a new node pointed by " u "   \\|/\n----------------------------------------------------------------------------------------------------\na | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z\n----------------------------------------------------------------------------------------------------\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t   \nNow time to store " d " of "bud".So now our trie looks like this :\n================================================================\n\n                 Root\n\t\t\t      |\n----------------------------------------------------------------------------------------------------\na | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z\n----|------------------------------------------------------------------------------------------------\n    |\n    |\n   \\|/    this is our new node which is being pointed by b\n----------------------------------------------------------------------------------------------------\na | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z\n--------------------------------------------------------------------------------|--------------------\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t|\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t|\n\t\t\t\t                                 a new node pointed by " u "   \\|/\n----------------------------------------------------------------------------------------------------\na | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z\n------------|----------------------------------------------------------------------------------------\n\t\t    |\n\t\t\t|\n\t\t   \\|/ a new node pointed by "d "\n----------------------------------------------------------------------------------------------------\na | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z\n----------------------------------------------------------------------------------------------------\nheyy wait , isnt this the end of the string ? yes?? so set **isend** to true for node \'d\' (which is\nbeing pointed by "u").\nIn a similar manner you will do insertion of other elements. Do a dry run on your own, you\nwill get it!! I am sure of it !!\n\nThis was the insertion part of it. But now how to search any element?\nSimple just pick up the character , go to its index by doing word[i]-\'a\' and check\nif it is null or not. if it is null, then that means that character is not present and return false\notherwise go furthur to the node which is pointed by that node. \nLets say if curr is the current node, then for moving further, do curr=curr->array_of_pointers[i] \ni refers to the current character which we are looking for.\nOk ok , i know , the next question is what to do if we have dot (.) , well in that case you need to check\nall the characters and perform the same traversal steps. \nOkayy, so far i think you have the prerequisite knowledge and now you can see the below code:\n\nstruct Trie{\n        Trie *arr[26];    //nothing fancy, bunch of pointers \n        bool isend;    // to mark the end of the string\n        Trie(){    //constructor to initialize all pointers to null intitally\n            for(int i =0;i<26;i++){\n                arr[i]=NULL;\n            }\n            isend=false;\n        }\n    };\n\nclass WordDictionary {\npublic:\n    /* \n    by reading the problem , one can easily guess that alternative solution is TRIE coz it\n    is a perfect data structure when you are dealing with prefixes or sufixes.\n    first things first , we need to create a TRIE \n    */\n    Trie *root;    //our mighty root node\n    \n    WordDictionary() {\n        root=new Trie();      //creation of the root node\n    }\n    \n    void addWord(string word) {\n        Trie *curr=root;                   \n        int length=word.size();\n        int index;\n        for(int i =0;i<length;i++){   //inserting the character one by one\n            index=word[i]-\'a\';\n            if(curr->arr[index]==NULL){       //if that character is not present, \n\t\t\t//then create a node and point to it and if it is already present (for example- you have inserted\n\t\t\t//"bad" and now you are inserting "bud", so b is already there, so you dont have to do anything\n\t\t\t//thats the beauty of trie\n                curr->arr[index]=new Trie();\n            }\n            curr=curr->arr[index];\n        }\n        curr->isend=true; //marking the end of the string\n    }\n    \n    bool searchUtilDFS(Trie *curr,string word){\n        //Note : we only need to perform dfs when we encounter dot\n        int length=word.size();\n        int index;\n        for(int i =0;i<length;i++){\n            if(word[i]!=\'.\'){  //simply traverse the TRIE\n                index=word[i]-\'a\';\n                if(curr->arr[index]==NULL){\n                    // that element doesnt exist\n                    return false;\n                }\n                curr=curr->arr[index];\n            }else{\n                //we encounter the dot operator\n                //so we need to consider all possibilities that is string starting from a,b,c,d,e....so on\n                bool result=false;\n                int j;\n                for(j =0;j<26;j++){  // to traverse string starting from a, b ,c , d and so on\n                    if(curr->arr[j]!=NULL)\n                    result=result|searchUtilDFS(curr->arr[j],word.substr(i+1)); \n                    if(result)return true;  \n                }\n                return false;\n            }\n        }\n       return curr->isend; // why we are returing this coz lets suppose\n\t   //we have " b u d d y " stored in trie and we are searching for " b u d " \n\t   //it should return false correct??  so when we are at d, return curr->isend \n\t   // will return false as it is not the end of the string.\n\t   \n    }\n    bool search(string word) {\n        //in searching part , we have to take care of the dot.\n        //if we are encountering dot then we can have to take all possible cases that is all 26 alphabets\n        //lets suppose we need to search a string like this b * d, so getting b is straight forward\n        //however for the next part *, we have to check all 26 alphabets which can possibly have\n        // d as the last character.\n        //lets see the code\n        Trie *curr=root;\n        return searchUtilDFS(curr,word);\n    }\n};\n\n/**\n * Your WordDictionary object will be instantiated and called as such:\n * WordDictionary* obj = new WordDictionary();\n * obj->addWord(word);\n * bool param_2 = obj->search(word);\n */\n ```\n \n Thanks for reading the whole explanation. Apologies if you got lost somewhere but try to dry run and\n you will have your way !!\n If it helped, dont forget to upvote !!\n Thanks !!!
['Tree', 'Depth-First Search', 'Trie', 'Recursion']