understood

Very well

bro could you please share the code for your implementation. i also tried to do the same by implementing the search function. but on one part i am struck. i need to check how you have implemented it

#include struct Node{ bool isend = 0; Node* hash[26]={NULL}; }; class Trie{ Node * root; public: Trie(){ root = new Node(); } void insert(string newword){ Node* node = root; for(auto it : newword){ if(!(node->hash[it-'a'])){ node->hash[it-'a'] = new Node(); } node = node->hash[it-'a']; } node->isend = 1; } bool is_pref(string searchword){ Node* node = root; for(auto it : searchword){ if(!(node->hash[it-'a'])) return 0; bool val = node->hash[it-'a']->isend; if(!val) return 0; node = node->hash[it-'a']; } return 1; } }; string completeString(int n, vector &a){ // Write your code here. Trie DS; for(auto it : a){ DS.insert(it); } vector possible_strings; string prev(""); bool flag = 1; for(auto it : a){ if(DS.is_pref(it)) { if(flag) {prev = it;flag = 0;} if(it.size()>prev.size()) prev = it; if(it.size()==prev.size()&&it

yes,you can do this as well

Finding length takes O(length) time which is similar to iterating it in Trie. So you can do whatever you want

@@Cool96267 I guess in C++ STL, string::length() is constant time operation

this will fail for many testcases which don't have all the substrings of the word, present in the array.

​@@nightmare_9i don't think so. Only way a word can end up in a map is if it's prefix of length - > n-1 exists in array and would have been stored already in the map. Now recursively apply this property to its prefix existing in the map. So finally we can conclude that only if all the prefixes of a given word exist in the array, then only the word will be considered as a possible answer and would be inserted into the map. Still if u have any particular test case where it can fail, then please share.

@Tarunkumar Gatla I checked on leetcode by giving several custom inputs to internal solution. Answer turns out to be "yes". If all strings have length 1 or there is string of length 1 present in the list, it can be considered for ans. The reason according to me is, you start with empty string and pick a string from list one by one such that your string must be prefix of the string from the list and they differ in length by 1.

@@shubham320 is this question available on leetcode

bro there is no need of checking /storing if the word ended, cuz as you are checking in increasing order of length, there is necessity that all prefixes till i-1 for that should be present. So it wont matter here. You can omit the isEnd attribute here.

@@vanshsehgal9475 Yeah you're right!

@@vanshsehgal9475 is this correct ? #include struct Node{ Node *child[26]; Node(){ for(int i=0; ichild[ind])) return false; if(word.length() == 1){ Node *child = new Node(); root->child[ind] = child; } // recursive call return check(root->child[ind], word.substr(1)); } public: Trie(){ root = new Node(); } bool checkStr(string str){ return check(root, str); } }; string completeString(int n, vector &a){ // Write your code here. sort(a.begin(), a.end()); Trie *t = new Trie(); string ans; for(int i=0; icheckStr(a[i])){ if(a[i].size() > ans.size()) ans = a[i]; } } if(!ans.size()) return "None"; return ans; }

``` import java.util.Scanner; public class Trie { private static class Node{ Node[] links = new Node[26]; boolean flag = false; boolean containsKey(char ch){ return links[ch -'a'] != null; } void put(char ch, Node node){ links[ch - 'a'] = node; } Node get(char ch){ return links[ch - 'a']; } void setEnd(){ flag = true; } boolean isEnd(){ return flag; } } private static Node root; public Trie(){ root = new Node(); } public static void insert(String word){ Node node = root; for(int i =0; i < word.length(); i++){ if(!node.containsKey(word.charAt(i))){ node.put(word.charAt(i), new Node()); } node = node.get(word.charAt(i)); } node.setEnd(); } public static boolean checkCompleteString(String word){ Node node = root; for(int i= 0; i< word.length(); i++){ if(!node.containsKey(word.charAt(i)) ){ return false; } node = node.get(word.charAt(i)); if(!node.flag){ return false; } } return true; } } class Solution { public static String completeString(int n, String[] a) { Trie trie = new Trie(); // insert all for(int i=0; i < a.length; i++){ trie.insert(a[i]); } String maxString = ""; // check for all strings for( int i = 0; i < n; i++){ // if string is complete string or not if(trie.checkCompleteString(a[i])){ if(maxString.length() < a[i].length()){ maxString = a[i]; } if ((maxString.length() == a[i].length()) && (maxString.compareTo(a[i]) > 0)) { maxString = a[i]; } } } if(maxString.isEmpty()){ return "None"; }else{ return maxString; } } } ```

Practice is important. You need to know what constructs to use in what situation. You cannot predict what they'll ask. I had prepared all my algos for Uber, and I couldn't write a simple currying function. 😅

@@rutwickgangurde3247 What was the question? Where have you been hired now?

@@rutwickgangurde3247 oh

The last substring.length() isn't under nested loop, it has an independent loop after insertion all the elements in the trie, hence O(n*avglen(input strings))

And.. I am studying tries now because I gave google's ot this sunday and tries qn was asked.. cldnt solve it lol ;-;

Thanks to you, I was able to get to optimize my code 👍. string longestWord(){ string res, path; dfs(path, res, this->root); return res; } void dfs(string &path, string &res, Node *root) { if(root == NULL || root->isEnd() == false) return; if(path.size() > res.size()){ res = path; } else if(path.size() == res.size()){ res = (path < res) ? path : res; } for(int i = 0; i < 26; i++){ path.push_back('a' + i); dfs(path, res, root->get('a' + i)); path.pop_back(); } }

your approach is correct. Lets calculate the Time complexity : O(n*logn) + O(n*len*logn) where len is avg leng of string, n*logn for inserting all strings in the map, and n*len*logn for taking each string, find substring and checking in the map, Wheres Trie approach takes 2*O(n*len),

@Virendra Negi Here is my understanding, correct me if I am wrong. The time complexity will be - O(N*len(s)*LogN). N - traversing all string len(s) - each substring in a string logN - search time in a map. search time for map - log(N) and unordered_map - O(1) average, O(N) (worse). "unordered_map worst case usually happens when the hash function is producing collisions for every insertion in the map." It might not happen often, but its a factor. I believe because of this Trie works better for larger cases, without any collisions and easy traversal. (but long code lol).

Thanks man!

this is giving wrong answer ...for every test cases it returns the none value.....

@@shikhagupta4429 bhai 1 saal pehle ka code hai, wo time shi chalra tha, ab kuch changes kr diye honge me kya kru, or tune video dekhi hai toh tere se khud se code na likha jara, mene bhi toh ye khud kiya