{"id":2261,"date":"2020-06-15T02:14:49","date_gmt":"2020-06-15T02:14:49","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=2261"},"modified":"2022-03-28T23:17:07","modified_gmt":"2022-03-28T23:17:07","slug":"find-words","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/find-words\/","title":{"rendered":"Find words"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

Trie<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Easy<\/p>\n<\/blockquote>\n

Problem Statement :<\/h3>\n
\n

Given a blank dictionary. Now in the first set of operations, you have to insert N integers in the dictionary. And then you have to find M words in the dictionary and print "Present" if the word is present and "Not" if the word is not present in the Dictionary.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Solution Approach :<\/h3>\n

Introduction :<\/h4>\n
\n

We will generate a tree<\/strong> with 26<\/code> outgoing nodes, for every alphabet. Insert every character as an individual node of the tree and mark where every word ends. This marking of word end will help us search a given word.<\/p>\n<\/blockquote>\n

Description:<\/h4>\n
\n

We will use trie<\/strong> to solve this problem.
\nA Trie<\/strong> is a special data structure used to store strings that can be visualized like a graph. It consists of nodes and edges. Each node consists of atmost 26<\/code> children and edges connect each parent node to its children. These 26<\/code> node pointers is for 26<\/code> letters of the English alphabet. A separate edge is maintained for every edge.
\nWe will insert<\/strong> every character of the word as individual node and now that we already know (from the definition above) that every node is a pointer to 26<\/code> different nodes which represents alphabets, we will determine if the input character is new or an extension of the previously inserted character. If it is new we will create a node and add it to the tree, otherwise we will keep inserting the character(node) , then mark the last character of the word being inserted, as the word end<\/strong>.
\nNow that we have inserted our words into the tree we will we given few other words whether they are present in the tree or not. We will search for every character , left to right, of the word (value to be searched). If every character is present and the last node of the tree (trie) which matches the last character of the word 9being searched) is the word end<\/strong>, then we can say its "Present" otherwise it is not.<\/p>\n<\/blockquote>\n

\"\"<\/p>\n

Algorithm :<\/h4>\n

insert()<\/strong>:<\/p>\n

    \n
  • iterate for every character in string, value<\/code>,<\/li>\n
  • check if the character previously being inserted,<\/li>\n
  • if not, make a new tree node for this character and add it as the children of the root.<\/li>\n
  • if it is already present, make the child node as parent and do the same with the remaining characters in value<\/code>.<\/li>\n
  • After inserting the last character node of value<\/code> in tree , mark that node as word end<\/strong>.<\/li>\n<\/ul>\n

    search()<\/strong>:<\/p>\n

      \n
    • iterate for every character c<\/code> in string, key<\/code>,<\/li>\n
    • if c<\/code> is not present, childern[c]==NULL<\/code>, return FALSE.<\/li>\n
    • else, if all c<\/code> are present and the current node is not NULL and current node is the word end<\/strong>, return TRUE.<\/li>\n<\/ul>\n

      Complexity Analysis :<\/h3>\n

      We are inserting the characters of length M<\/code>, lets say. Also we are searching for M<\/code> character array at a time for a single query.<\/p>\n

      Space complexity<\/strong> of this data structure would be O(26*M*N)<\/code>, where M<\/code> is the length of the string , N<\/code> is the number of nodes in trie.<\/p>\n

      Solutions:<\/h3>\n

      \t\t\t\t\t\t