Small correction in calling the function checkIfPrefixExists : It should be trie.checkIfPrefixExists(it) //Not just checkIfPrefixExists(it) And Thank U Striver for taking us forward!
In function isPrefix, we dont need to check if the word exists in the trie we just need to ensure that every node has flag value true because we are not asked to search for a new word.
Understood, Thanks a lot. Implemented it on my own and this is how I did it: I used the search function of trie, and instead of traversing through nodes, and I checked for the string only if it is larger than the previous largest one, another thing is that in Java I stings are immutable, so I stored the index of the largest string instead of the largest string itself.
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
I don't how i come up to this approach but it is working USED RECURSION TC -(n * m^2) n for the main for loop and m for the rec and m for the .find(); you can use the unordered set the TC -O(n*m); sc-O(n) + m -->n for the set and m for the recursion stack space bool rec(int idx, string str, set& st, string word) { if (idx >= word.size()) { return true; // Base case: all characters have been processed } str += word[idx]; if (st.find(str) == st.end()) { return false; // If prefix not found, return false } return rec(idx + 1, str, st, word); } string completeString(int n, vector& a) { set st(a.begin(), a.end()); string valid = ""; for (int i = 0; i < a.size(); i++) { string str=""; if (rec(0, str, st, a[i])) { // Update valid string based on size and lexicographical order if (a[i].size() > valid.size()) { valid = a[i]; } else if (a[i].size() == valid.size() && a[i] < valid) { 0 ? valid : "None"; }
Another solution for this question using maps:- string completeString(int n, vector &a){ sort(a.begin(),a.end()); string ans = ""; unordered_mapm; m[""]++; int count = 0; for(auto i : a){ string temp = i.substr(0,i.size()-1); if(m[temp]!=0){ if(ans.size()
@@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.
Just a question, while iterating each input in completeString function Why don't you simply skip it if it's length is lower than current answer candidate. Why to even check if prefix exists or not.
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.
time complexity should be: O(n* it.length() * sub.string.length()) n= for traversing the array it.length()= for all substring of a[i] substing.length()= when we are checking it in trie is it existing or not ? little confusion😥😥
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))
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. 😅
Understood Please make a video on the topic, "WHAT TYPE OF QUESTIONS ARE ASKED IN INTERSHIP ROUNDS OF BIG COMPANIES" And how should we prepare from them...
Wo cheez jisko dekh kar kabhi dar lagta tha,aur wo samajh aane laga to feeling hi kuch aur hoti hai.Aisa lagta hai jaise ab apna bhi kuch ho sakta hai😅
I didn't understand what exactly are we checking in check if prefix exist function, and why did we write if node is a terminal then return false? Can someone explain please?
Here is my c++ code for this same problem. I did a dfs-like traversal on the trie. Guess it will be a bit more optimal than checking if prefix exists each time P.S : I names links as ref and flag as end. Its not industry standard as Boss Striver has done. Love ur content man ♥ struct Node{ Node* ref[26]; bool end; Node(){ for( int i=0; iend == false ) return;
// some string has ended here if( path.size() > res.size() ) res=path;
// move to the next char for( int i=0; iref[i]!=NULL ) { path+=('a'+i); get_ans( root->ref[i], res, path ); path.pop_back(); } } } string completeString(int n, vector &a){ // Write your code here.
// create a trie Node* root=new Node(); root->end=true;
// inserting each string into trie for( auto str: a ){ Node* curr=root; for( auto c: str ){ if( curr->ref[c-'a']==NULL ) curr->ref[c-'a'] = new Node(); curr = curr->ref[c-'a']; } curr->end=true; }
from typing import * from collections import defaultdict class Trie: def __init__(self): self.child = defaultdict(Trie) self.end = False def insert(self,word): cur=self for i in word: cur=cur.child[i] cur.end=True def search(self,word): cur=self for i in word: if i not in cur.child: return False cur = cur.child[i] return cur.end def checkLongest(self,word): cur = self for i in word: cur=cur.child[i] if not cur.end: return False return True
def completeString(n: int, a: List[str])-> str: trie = Trie() for i in a: trie.insert(i) ans="" for i in a: if trie.checkLongest(i): if len(ans)
Can't we use a map here? I haven't yet solved the qs and I am halfway through the video but my intuition is saying to use the map insert all the strings in the map and for each string create the prefix using substr fn and check whether the prefix is present or not. we may avoid that extra time complexity of inserting each string in a trie O(N)*O(len) where len is the average length of the string. I may be wrong
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).
@@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
Lets start a new trend, please comment "understood" in case you did :)
understood
Small correction in calling the function checkIfPrefixExists :
It should be trie.checkIfPrefixExists(it) //Not just checkIfPrefixExists(it)
And Thank U Striver for taking us forward!
In function isPrefix, we dont need to check if the word exists in the trie we just need to ensure that every node has flag value true because we are not asked to search for a new word.
Understood, Thanks a lot.
Implemented it on my own and this is how I did it:
I used the search function of trie, and instead of traversing through nodes, and I checked for the string only if it is larger than the previous largest one, another thing is that in Java I stings are immutable, so I stored the index of the largest string instead of the largest string itself.
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
I don't how i come up to this approach but it is working
USED RECURSION
TC -(n * m^2) n for the main for loop and m for the rec and m for the .find();
you can use the unordered set the TC -O(n*m);
sc-O(n) + m -->n for the set and m for the recursion stack space
bool rec(int idx, string str, set& st, string word) {
if (idx >= word.size()) {
return true; // Base case: all characters have been processed
}
str += word[idx];
if (st.find(str) == st.end()) {
return false; // If prefix not found, return false
}
return rec(idx + 1, str, st, word);
}
string completeString(int n, vector& a) {
set st(a.begin(), a.end());
string valid = "";
for (int i = 0; i < a.size(); i++) {
string str="";
if (rec(0, str, st, a[i])) {
// Update valid string based on size and lexicographical order
if (a[i].size() > valid.size()) {
valid = a[i];
} else if (a[i].size() == valid.size() && a[i] < valid) { 0 ? valid : "None";
}
Understood and did it myself before watching this. All thanks to striver. ❤
UNDERSTOOD.....Thank You So Much for this wonderful video......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Another solution for this question using maps:-
string completeString(int n, vector &a){
sort(a.begin(),a.end());
string ans = "";
unordered_mapm;
m[""]++;
int count = 0;
for(auto i : a){
string temp = i.substr(0,i.size()-1);
if(m[temp]!=0){
if(ans.size()
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.
sorting the strings make the time complexity as O(nlogn), but with tries, we can do this in O(n) itself.
skip to 19:50 if you have seen L1 for trie implementation.
Just a question, while iterating each input in completeString function
Why don't you simply skip it if it's length is lower than current answer candidate. Why to even check if prefix exists or not.
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
as the constraints are 1
Bhaiya bahaut badhiya samjhaye hain aap. Thanks 👍🙌
wonderful just wonderful !!
This is not optimal, since we are checking for each prefix from start, doing dfs would work fine.
Understood everything, thanks bhaiya.
string striver_Best_Explanation = "Understood";
cout
Hello Striver! Thanks for all your videos.
I don't think we have to write another function to check prefixes, we can check while inserting if already sort the strings by length, even it reduces complexity by a greater amount.
My implementation of the idea, which passed all cases in code studio also:
struct Node{
vector children;
bool isEnd;
Node(){
children.assign(26, NULL);
isEnd = false;
}
bool containsKey(char ch){
return children[ch - 'a']!=NULL;
}
void put(char ch, Node* node){
children[ch - 'a'] = node;
}
Node* get(char ch){
return children[ch - 'a'];
}
};
class Trie{
private:
Node* root;
public:
Trie(){
root = new Node();
}
bool insertAndCheck(string word){
Node* node = root;
for(int i=0; icontainsKey(word[i]) && node->isEnd){
node = node->get(word[i]);
} else {
return false;
}
}
node->put(word[word.length()-1], new Node());
node->isEnd = true;
return true;
}
};
string completeString(int n, vector &a){
sort(a.begin(), a.end(), [](string x, string y){return x.length() < y.length();});
string longest = "";
Trie obj;
for(string word : a){
if(obj.insertAndCheck(word)){
if(word.length() > longest.length()){
longest = word;
} else if(word.length() == longest.length() && word < longest){
longest = word;
}
}
}
return (longest == "" ? "None" : longest);
}
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;
}
bhaiya has further made the code more readible, follow the link in the description
Understood thanks a lot
Understood
Keep em coming 🔥🔥
understood!! Great Problem & explanation. Thanks:)))!!!
superb explanation!
time and space complexity : 12:30
understood "Awesome Playlist"
time complexity should be: O(n* it.length() * sub.string.length())
n= for traversing the array
it.length()= for all substring of a[i]
substing.length()= when we are checking it in trie is it existing or not ?
little confusion😥😥
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))
Thank you 🙏
Is your graph n trees series enough to crack tech interviews of tech giant's (for DSA beginners)
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
Understood
Please make a video on the topic, "WHAT TYPE OF QUESTIONS ARE ASKED IN INTERSHIP ROUNDS OF BIG COMPANIES"
And how should we prepare from them...
understood, thanks for the code explanation
understooooood bhaiya. thanks 🙂
Please make this solution avaialble on the website .
Understood:)
Can anyone please tell me,
What software he’s using to write on this blackboard 9:47
Understood 😊
Hey Striver, you gave c++ solution in java solution link. Can you please provide java solution?
```
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;
}
}
}
```
Instead of checking for every word, we can do a dfs on the trie
understood bhaiya
thank you
cant we just bfs through the trie (only the nodes which are marked true)? It will have tc of O(len)
in the worst case its tc will still be O(sum of all lengths of the string) as you will be required to traverse every node
Wo cheez jisko dekh kar kabhi dar lagta tha,aur wo samajh aane laga to feeling hi kuch aur hoti hai.Aisa lagta hai jaise ab apna bhi kuch ho sakta hai😅
Ye question set se zada simply nhi hojaega?
undestood
Hare Krishna!
Thanks dude
I think line number 52 must be inside else statement
Hi Striver, don't we need to consider the time complexity for comparing lexicographically smaller string after checkIfPrefixExists is true?
Python Code for fellow pythonista :-
class Node():
def __init__(self):
self.links=[None]*26
self.flag=False
def get(self,ch)-> 'Node':
return self.links[ord(ch)-ord('a')]
def put(self,ch,node):
self.links[ord(ch)-ord('a')]=node
def contains(self,ch):
return self.links[ord(ch)-ord('a')]!=None
def setEnd(self):
self.flag=True
def isEnd(self):
return self.flag
class Trie():
def __init__(self) -> None:
self.Trie=Node()
def insert(self,word):
node=self.Trie
for i in word:
if(not node.contains(i)):
node.put(i,Node())
node=node.get(i)
node.setEnd()
def checkPrefixExists(self,word):
node=self.Trie
for i in word:
if(node.contains(i)):
node=node.get(i)
if(node.isEnd()==False):
return False
else:
return False
return True
if __name__=='__main__':
trie=Trie()
prefixes=['n','ni','nin','ninj','ninja','ninga']
for i in prefixes:
trie.insert(i)
longest=''
for i in prefixes:
if(trie.checkPrefixExists(i)):
if(len(longest)
Understood, thanks
Hi Striver, your Java code is still written in C++. Could you please replace it with Java Code.
Understood brother
Thanks
I didn't understand what exactly are we checking in check if prefix exist function, and why did we write if node is a terminal then return false? Can someone explain please?
Understood 🙌
understood!
Understood 😊😊😊😊
Understood!
"understood" :)
Hello striver, The java github link for this question is also having c++ code... please update it...
understood
understood!!
Here is my c++ code for this same problem. I did a dfs-like traversal on the trie. Guess it will be a bit more optimal than checking if prefix exists each time
P.S : I names links as ref and flag as end. Its not industry standard as Boss Striver has done. Love ur content man ♥
struct Node{
Node* ref[26];
bool end;
Node(){
for( int i=0; iend == false ) return;
// some string has ended here
if( path.size() > res.size() ) res=path;
// move to the next char
for( int i=0; iref[i]!=NULL ) {
path+=('a'+i);
get_ans( root->ref[i], res, path );
path.pop_back();
}
}
}
string completeString(int n, vector &a){
// Write your code here.
// create a trie
Node* root=new Node();
root->end=true;
// inserting each string into trie
for( auto str: a ){
Node* curr=root;
for( auto c: str ){
if( curr->ref[c-'a']==NULL ) curr->ref[c-'a'] = new Node();
curr = curr->ref[c-'a'];
}
curr->end=true;
}
// findind answer
string res, path;
get_ans( root, res, path );
if( res.size()==0 ) res="None";
return res;
}
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();
}
}
bool checkAllPrefixExist(string &word)
{
TrieNode* cur = root;
for(auto &ch : word){
if(cur->links[ch-'a']!=NULL){
cur = cur->links[ch-'a'];
if(cur->isEnd==false)
return false;
}
else
return false;
}
return true;
}
U
N
D
E
R
S
T
O
O
D
understood..
Understood
I already solved the question before seeing the video but i see the video later anyways xD
understood sir
Hi Striver
Thanks a lot for making these videos.
Could you please tell me which application you use to make these videos ?
from typing import *
from collections import defaultdict
class Trie:
def __init__(self):
self.child = defaultdict(Trie)
self.end = False
def insert(self,word):
cur=self
for i in word:
cur=cur.child[i]
cur.end=True
def search(self,word):
cur=self
for i in word:
if i not in cur.child:
return False
cur = cur.child[i]
return cur.end
def checkLongest(self,word):
cur = self
for i in word:
cur=cur.child[i]
if not cur.end:
return False
return True
def completeString(n: int, a: List[str])-> str:
trie = Trie()
for i in a:
trie.insert(i)
ans=""
for i in a:
if trie.checkLongest(i):
if len(ans)
Can't we use a map here? I haven't yet solved the qs and I am halfway through the video but my intuition is saying to use the map insert all the strings in the map and for each string create the prefix using substr fn and check whether the prefix is present or not. we may avoid that extra time complexity of inserting each string in a trie O(N)*O(len) where len is the average length of the string. I may be wrong
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).
"understood"
Java solution k jga syd apne c++ dal dia h
uderstood :-)
but what about this example ni , nin , ninj, ninja , ningass its give 0 becouse for n its not true
If there was one more input for the first sample test case, they would have written the N - word.
UnderStood++;
"Understood"
this code give wrong answer
can we do this by sorting like this:
/*
#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;
}
*/
thnx i did this on my own, code:
#include
struct Node{
Node* links[26];
bool isTerminal=false;
bool containsKey(char ch){
return links[ch-'a']!=NULL;
}
void puts(char ch){
links[ch-'a']=new Node();
}
Node* gets(char ch){
return links[ch-'a'];
}
};
class Trie{
Node* root;
public:
Trie(){
root= new Node();
}
void insert(string& str){
Node* node= root;
for(int i=0;icontainsKey(str[i])){
node->puts(str[i]);
}
node=node->gets(str[i]);
}
node->isTerminal=true;
}
int checkSize(string& a){
Node* node= root;
int count=0;
for(int i=0;igets(a[i])->isTerminal){
return 0;
}else{
count++;
}
node= node->gets(a[i]);
}
return count;
}
};
string completeString(int n, vector &a){
// Write your code here.
Trie t1;
for(auto it: a){
t1.insert(it);
}
int size=0;
string ansString="";
for(int i=0;i
java simple code
class Solution {
static class trie{
boolean isEnd = false;
trie[] children = new trie[26];
}
static trie root;
public static String completeString(int n, String[] a) {
root = new trie();
for(String str : a){
insert(str);
}
String longest = "";
for(String word : a){
if(checkIfAllPrefixExists(word)){
if(word.length() > longest.length()){
longest = word;
}
else if((word.length() == longest.length()) && word.compareTo(longest) < 0){
longest = word;
}
}
}
return longest == "" ? "None" : longest;
}
public static boolean checkIfAllPrefixExists(String word){
trie node = root;
boolean flag = true;
for(char ch : word.toCharArray()){
if(node.children[ch - 'a'] != null){
node = node.children[ch - 'a'];
flag = flag && node.isEnd;
}
else return false;
}
return flag;
}
public static void insert(String word){
trie node = root;
for(char ch : word.toCharArray()){
if(node.children[ch - 'a'] == null){
node.children[ch - 'a'] = new trie();
}
node = node.children[ch - 'a'];
}
node.isEnd = true;
}
}
// getting tle
struct Node{
Node *list[26];
bool flag=false;
bool containsKey(char ch) {
return list[ch-'a'] != NULL;
}
void put(char ch, Node *node) {
list[ch-'a'] = node;
}
Node* get(char ch) {
return list[ch-'a'];
}
void setEnd() {
flag = true;
}
bool isEnd() {
return flag;
}
};
class Trie {
private: Node *root;
public:
Trie() {
root = new Node;
}
void insert(string word) {
Node *node = root;
for(int i=0;icontainsKey(word[i])) {
node->put(word[i],new Node);
}
node = node->get(word[i]);
}
node->setEnd();
}
bool checkIfPrefixExists(string word) {
Node *node = root;
bool f = true;
for(int i=0;icontainsKey(word[i])) {
node = node->get(word[i]);
f = f&node->isEnd();
}
else {
return false;
}
}
return f;
}
};
string completeString(int n, vector &a){
// Write your code here.
Trie* obj = new Trie();
for(auto it:a){
obj->insert(it);
}
string longest = "";
for(auto it : a) {
if(obj->checkIfPrefixExists(it)) {
if(it.size()>longest.size()){
longest = it;
}
else if(it.size()==longest.size() && it
Thanks man!
ninga
us
struct Node {
Node* links[26];
bool flag = false;
bool containskey(char ch) {
return links[ch - 'a'] != NULL;
}
Node* get(char ch) {
return links[ch - 'a'];
}
void put(char ch, Node* node) {
links[ch - 'a'] = node;
}
void setend() {
flag = true;
}
bool isend() {
return flag;
}
};
class Trie{
private: Node* root;
public:
Trie(){
root=new Node();
}
public: void insert(string word){
Node* node =root;
for( int i=0;i< word.length();i++){
if( !node->containskey(word[i])){
node->put(word[i],new Node());
}
node=node->get(word[i]);
}
node->setend();
}
public:
bool check(string word){
Node* node = root;
bool flag=true;
for (int i = 0; i < word.length(); i++) {
if (node->containskey(word[i])) {
node = node->get(word[i]);
if (node->isend()==false) return false;
}
else {
return false;
}
}
return true;
}
};
string longestCommonPrefix(vector &arr, int n)
{
Trie trie;
for (auto& it : arr) {
trie.insert(it);
}
string longest = "";
for (auto& it : arr) {
if (trie.check(it)) {
if (it.length() > longest.length()) {
longest = it;
} else if (it.length() == longest.length() && it < longest) {
longest = it;
}
}
}
if (longest == "") return "None";
return longest;
} This code returns the None value for all the test cases!! can anyone telll me what's the issue ??
Understood thnks...
#include
struct Node{
Node* links[26];
bool flag = false;
bool 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;
}
bool isEnd(){
return flag;
}
};
class trie{
private:
Node* root;
public:
trie(){
root = new Node();
}
void insert(string word){
Node* node = root;
for(int i=0; icontainskey(word[i])){
node->put(word[i],new Node());
}
node = node->get(word[i]);
}
node->setEnd();
}
bool search(string word){
Node* node = root;
for(int i=0; icontainskey(word[i])){
return false;
}
node = node->get(word[i]);
}
return node->isEnd();
}
};
bool cmp(string s,string ans){
int i=0 , j=0;
while(i
why do you make such accent? it feels annoying...
c++ working code
.
.
.
#include
struct Node{
Node* links[26];
bool flag = false;
bool conatinsKey(char ch){
return (links[ch-'a']!=NULL);
}
Node* get(char ch){
return links[ch-'a'];
}
void put(char ch, Node* node){
links[ch-'a'] = node;
}
void setEnd(){
flag = true;
}
bool isEnd(){
return flag;
}
};
class Trie{
private:
Node* root;
public:
Trie(){
root = new Node();
}
void insert(string word) {
Node *node = root;
for (int i = 0; i < word.size(); i++) {
if (!node->conatinsKey(word[i])) {
node->put(word[i], new Node());
}
node = node->get(word[i]);
}
node->setEnd();
}
bool checkAllPrefixExist(string &word)
{
Node* cur = root;
for(auto &ch : word){
if(cur->links[ch-'a']!=NULL){
cur = cur->links[ch-'a'];
if(cur->isEnd()==false)
return false;
}
else
return false;
}
return true;
}
};
string completeString(int n, vector &a){
Trie trie;
for(auto it:a){
trie.insert(it);
}
string longest = "";
for(auto it : a) {
if(trie.checkAllPrefixExist(it)) {
if(it.size()>longest.size()){
longest = it;
}
else if(it.size()==longest.size() && it
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
Single pass C++ code:
#include
struct Node
{
Node* links[26];
int ew=0; //if any word is ending at this node
void put(char ch, Node* node)
{
links[ch-'a']=node;
}
};
string completeString(int n, vector &a){
sort(a.begin(),a.end());
Node* root=new Node();
root->ew=1;
int anslen=0;
string ans;
for(int i=0;iput(word[j], new Node());
if(temp->ew ==0)
flag=false;
temp=temp->links[word[j]-'a'];
}
temp->ew += 1;
if(flag==true)
{
if(word.size()>anslen)
{
anslen=word.size();
ans=word;
}
}
}
if(ans=="")
return "None";
return ans;
}
understood!
Understood!
thanks
understood!!
Understood
understood
U N D E R S T O O D
understood!!!
Understood
understood
understood!!!
Understood