G-26. Alien Dictionary - Topological Sort
ฝัง
- เผยแพร่เมื่อ 21 ก.ย. 2024
- GfG-Problem Link: bit.ly/3C9N6ZU
C++/Java/Codes and Notes Link: takeuforward.o...
DP Series: • Striver's Dynamic Prog...
SDE Sheet: takeuforward.o...
Check out our Website for curated resources:
Our Second Channel: / @striver_79
In case you are thinking to buy courses, please check below:
Code "takeuforward" for 15% off at GFG: practice.geeks...
Code "takeuforward" for 20% off on sys-design: get.interviewr...?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/inv...
Take 750 rs free Amazon Stock from me: indmoney.oneli...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v...
Linkedin/Instagram/Telegram: linktr.ee/take...
---------------------------------------------------------------------------------------------------------------------------
![[LIVE] : ONE ลุมพินี 80 | คู่เอก "รักษ์ vs ยอดนำชัย"](http://i.ytimg.com/vi/ckLMRorsMeY/mqdefault.jpg)
Let's continue the habit of commenting “understood” if you got the entire video. Please give it a like too, you don't 😞
Do follow me on Instagram: striver_79
The leetcode version of this prob doesn't say " k starting alphabets of standard dictionary" - so is it expected to take a list of size 26 ???
One more thing that I learned from Striver is writing correct code in one go , without any errors !!
It come from practice
❤
@@lalitagarwal9155 he was a CM on codeforces when it wasnt even that famous.
@@lalitagarwal9155 lol if you were one then you would have known and wouldnt say that
Have you ever heard of editing....just kidding. I was also surprised when I saw that no compilation error is there. But at few places he just resolved the compilation error and edit that part to save the time...but there was some.
I always feared Graph and DP, until I started studying them. You made it so simple! Thank u striver!!
One important note :
For concatinating characters in a string variable, use either of the 2 techniques :
string st;
1. st+=ch;
2.st.push_back(ch);
Using st=st+ch; creates a new object everytime and we might get a time limit exceeded error.
there will be no TLE coz the max string length will be 26.. but the above methods are recommended
Nope, st+=ch is basically the same, just use push_back or append, they are better
Understood! Thanks man, you truly are a gem. I just want to add a single to your solution as the above solution did not work for the test case "10 9
dhhid dahi cedg fg gdah i gbdei hbgf e ddde". I think this is newly added test case. Since while you were running only 1102 test cases were there, but currently there are 1118 test case. I have put a check if(topo.size()==K) before converting topo ArrayList to String. And then all the test cases passed.
Thanks for sharing ☺️.I am struggling for 2 hrs as I missed this check.
U make LeetCode hard problems damm easy man ❤️ U r god for us ❤️ Thanks a lot striver ❤️
watched just 4 minutes and solved the problem . love you bhaiya . your teach very good.
I had got the intuition within 6mins of the video and coded it correctly. @striver you are🔥🔥🔥
cant express the feeling in words striver i am able to solve this hard level problem by myself just bcoz of you
Understanding the Alien Dictionary Problem
00:08The problem involves finding the order of characters in an alien language given a dictionary.
00:17The order of characters in the alien language is not the same as the English language.
04:07
Applying Topological Sort Algorithm to Solve Alien Dictionary Problem
04:09The problem involves determining the correct order of alphabets in an alien dictionary.
04:15The topological sort algorithm can be applied to solve this problem.
05:02By creating a directed graph and analyzing the relationships between alphabets, the correct order can be determined.
08:11
Creating a Directed Graph and Performing Topological Sort
08:13Pairs of letters are used to create a directed graph, where the order is determined by the alphabet's relative size.
10:12The topological sort algorithm can be used to determine the order of the letters in the graph.
12:14
Implementing a Dictionary Order Algorithm
12:16Explanation of how to implement the algorithm
12:21Comparing strings and adding edges to create a dictionary order
13:03Iterating through pairs of strings and comparing characters
16:17
Finding Order in a Dictionary and Identifying Invalid Dictionaries
16:17By subtracting 'a' from the numbers 0, 1, and 2, they can be converted into characters.
16:22To create the graph, a constructive algorithm is used.
16:29To determine if an ordering is possible, the topological sort function is used.
you got a ❤ from tuf
understood striver
your way of explaining questions is just 🔥🔥🔥🔥
Should we be expected to figure out that it's a graph based problem just by looking at it? Just bcoz this problem is in the graph playlist, I could think in the direction of topo sort. Or else I would have never got an idea to solve such a complex problem.
while solving topo sort.....you should have got a "feeling" that when something is prioritized over others we can use the concept of topo sort, to get the complete priority order..... (if didn't get the "feeling" then you should try for getting it) So now when you see this question and understand it then try solving it and then again you will get the same kind of "feeling" ...(prioritizing something over other) then due to that "feeling" you brain will click for this approach....
@@SatyamEdits absolutely correct.
if there are dependencies between things, you should think about graph. This intuition will come through practice
@@Dontpushyour_luck Thats a great one. Thanks bro!
@@SatyamEdits Right man!! Thank you
Matlab ekdum maja hi agaya, adbhoot explanation :)
Following your playlist and wanted to say White background for java code is better 🙂🙂
did this on my own too, thank you striver.
Had tried solving the problem on my own, however I got a TLE on test case 423, then came to this video, and found out what I had to optimise. For every word in dict, I was comparing it with all subsequent words, when what I had to do was simply compare it with only the next word.
There can be one more edge case if only 1 word is given in the dictionary, then the topo sort will be empty as per the code. Also if k = 1, we can say that the ordering will contain only that letter
understood. I did this question 80% by myself, I got the confidence.
I am happy to say that I was able to solve this question all by myself.
Understood sir,You really deserve a whole universe of respect
Thank God, I am able to find a guy called Striver on youtube..... Thanks so much for all you do
Understood! Such a fantastic explanation as always, thank you very much!!
Best Graph series ever made
Solved this without looking at the video😀 Gaining confidence in graphs... Thanks STRIVER❤
I figure out the approach, coded it, but got segmentation fault, after three wrng submission I jumped to the striver's code, a and found a silly mistake in my code.
Thanks striver. I was able to code it on my own after your fabulous explanation.
you are so awesome i did this question myself after watching your previous videos
Thank You So Much for this wonderful video.............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Hey i have a doubt consider the case:
N = 3, K = 5
["aab", "bdec", "caa"]
Then in this case the character d and e, where they should come in the order.....
think of it , after creating adj a->b->c d e, so we can see a, d, and e have 0 indegrees so we can tell according to given data,
a d e can be in any order but b will come after a and c will come after b so valid orders are adebc, aedbc, daebc, deabc, eadbc, edabc.
One important note : for this case :
3 3
bbbbc bba aaaaac
adj[0]={};
adj[1]={0 (while comparing string 1 & 2) , 0 (while comaring string 2 & 3) };
so the created adj[1] have two 0 insted of one 0. it will give right answer, we don't have to remove all duplicates .
understood striver
made that hard problem look Easy
hats off to you
solved it by myself..Thanks sir. lots of love😃
Bhaiyaa, thank you so much for graph series, per bhaiya please can you also make series on segement trees, tried learning from so many places, but nowhere satisfactory content is found, bana do na bhaiya ek series please
did without watching video thanks bhaia
the new playlist is just fire
I was watching his video and his another video notification popped out 😂
Watching the video, I had the same question, I was wondering what if one of the strings is bigger and all the characters are the same except the last one of the bigger string, how will we compare them? However, you explained it so well at the end, thank you so much.
Made it too easy Sir! 🤩
Understood
Who said graphs is tough?? we have the chief... anyways gng to solve this particular problem its very easy. We have to get the sequence (or) order out of the string provided. So we make a graph out of them. Then we have to get the sequence pattern from start to end out of that graph hence we use the topological sorting.
Steps in topological sorting :
1. Get the indegree of all the nodes because we think like the initial node will have the 0 indegree even if we have the different components.
2. now take the nodes with zero indegree store them into the queue.
3. Then perform the BFS over the graph and visit their adjacent nodes and break the links that we have made. Indirectly reduce the indegree.
4. once the indegree becomes zero it means that we have traversed the links coming towards that node.
5. Do we will insert that also in the queue to traverse the adjacent nodes of newly added node.
Then return that graph . Incase of any queries check the topological sort from striver.
this solution is working as a b c and d correspond to 0 1 2 3, but what if letters were different like w, x, y, z in that case, nodes will be 22 23 24 25, so I think the toposort logic needs to accomodate that.
@takeUforward
understood
dude camera quality is better than its screen recording
Thank you bhaiya
super great striver!!
now i am able to solve many questions on my own thanq sir
Took me 3hrs to do it in java from leetcode where n & k are not given 😅
Incase if you donot understand the video for the first two minutes pause the video and think of how the dictionary will be.. baa, abcd are the two different words. baa is occurring before the abcd means b is before a in their dictionary. But if you also see b is occurring after a in second one. But that is allowed if you see the words in dictionary.
Dsa driver one and only striver❤
Understood 100% thanks bro 😊
What if the input is "abc" and "abcd" How will the graph be made?
There will be no graph. Just 4 nodes, ans no edges (a) (b) (c) (d). They all have indegree 0 so they will be printed in order.
Thank You. Very good explanation
this is a awesome application program on topo sort
nice question and great implementation of topo sort
Understood!
understood bhaiya
Understood!! very well explained!!!
Understood, Thank you very much!
Thank you, Striver 🙂
Understood Sir, Thank you very much
What if the dictionary has some character in which precedence is like this g->z->a->i and K=4 as for the aliends these are their first 4 word characters. Now my question is when we are making adjacency list for them then when we do s1[x] - 'a' for example then it will give an index which might be greater than size of our adjacency list.
Like here we make adj[K] what if the index so generated is greater than K . Why it is not giving error?
in the question it's already given that 'K' refers to the starting alphabet characters of a normal dictionary
So, when u take k=4 , it should contain {a,b,c,d} not {g,z,i}.
@@abhishek__anand__ what if the alien dictionary is not restricted to just first K alphabets of normal dictionary??? Like the question 269 in leetcode??
AMAZINGGG STRIVVERRR!! Thank youuu!!!
Thank you sir 😊
#Striver rocks 🤟👍
I have a doubt that what if we have a dictionary of two
as str[0]=abcd
and str[1]=bdc
your code for creating graph for dictionary will make a--->b only but the graph should be like a--->b--->d
so i think we should do
if (str1[ptr]==str2[ptr])continue;
else
adj[str1[ptr]].push_back(str2[ptr]) ;
Striver's code will also work
Graph created a-->b and then break stmnt gets executed
now we'll push in the queue where indegree=0 so a,c,d gets pushed in the queue and thus gets included in our soln
d shouldn't be in the graph as such bcz adc may appear before abc so b->d should be there instead so we can't figure out order on our own as it's alien dicti.
Understood , thank you so much.
Great Explanation thank you
what if we encounter an edge multiple times , it affects indegree doesnt it?
Great Explanation
Gr8 explanation as always!
Habibi ek baar fir se mast explanation thi tumhari ....ye waali aadhi khud karli thi apan ne logical view but not completely ..thanks habaibi ...understood
Regarding the follow-up question,
If there exists a cyclic dependency in the graph, doesn't the topoSort algorithm already handle this case?
So we just have to check for the first case where larger length string appears before the shorter length string.
Am I correct?
yes u r correct
Great explanation Striver!! I have a small doubt here why are we comparing only the adjacent strings, why are we not comparing a string with all the strings which are below it. In case if we just compare only the adjacent strings we might not get enough info right!! Waiting for your responce. Thankyou in advance!!
Here we are not trying to sort. We need to find the alien dictionary sorting means the given input already sorted according to the aliens. We just need to find the concurrent alphabets according to the aliens (given input)
im confused in first edge case mentioned bhiya said it is not possible if s1 is larger then it is not possible what does it mean
there are test cases like {"baa","abcd","abca","cab","cad"} here index 2 is larger string that index 3 string so is this invalid???
feeling so dumb not even understanding test cases 😵😵
Please anyone help.
Understood mann
Striver, thank you for this! quick question: what if the input is two same elements? then the adjacency will skip adding right? but the input is valid
then u just return the string itself.
Great explaination
The leetcode version of this prob doesn't say " k starting alphabets of standard dictionary" - so is it expected to take a list of size 26 ???
"understood"
perfect
striver i have one doubt
we are comparing only ith and i+1 th strings but why not we are trying out all the two possible combinations to figure out the order?
i could not understand how are we actually getting the order without doing that
say for example if alien order is a ,c ,e
given strings:
acc
caa
cac
cce
how will this i and i+1 work here?
because that doesn't make sense , strings are sorted on the basis of first different character according to your way we will get a cycle in first comparison only a->c then c->a and c->a
@@gautamgupta7148 we will not get cycle, acc and caa will give a->c, caa and cac will also give a->c, cac and cce will also give a->c
done and dusted
Wow! Well explained
UNDERSTOOD!!!!!!!!!!!!!!!
Great Explanation!
Thankyou sir🙇♂🙏❤ understood
understood thanks sir !❤❤
something before something 😂
Jokes apart, Great job🙌
understood striver
Hey Striver, I have a question related to optimisation.
What if the size of dictionary is large. Is it necessary to have to iterate over the whole dictionary even when the relationship of the letters could be determined by just iterating over the first ten words. Is there a way we can avoid this based on the current state of the relationship graph or something else?
Example, N= 10000000, k=5
["b","c","d","a","e","ee","eee","eeee","eeeee","eeeeee", ... so on till 10000000 entries]
as we can see, there are only 5 letters in the alphabet and their order is found within first few words of the dictionary. Please provide your suggestions/solutions for optimisation.
Highly appreciate your work. Thank you!
As in the above example , yes u can determine the ordering in the above case because ur input is skewed , consider this input ["b","c","d","a","e","ee","eee","eeee","eeeee","eb"] here u would find cycle when u iterate on eb , so we have to iterate over the whole dictionary because u have to cover all the possible edges . I hope this helps
understood🌺🌺
Understood On the way to master Graphs...
Understood Bhaiya
Thanks for the video. but test case:- {"baa", "abcd", "abca", "cab", "cade"} n = 5 and k=5 is returning "b e d a c" while it should be "bdace" right ? Thanks.
nope order of 'e' doesn't matter, you can place it anywhere since no one is associated with it. just take care of which are actually in DAG
ig whether you apply BFS or DFS your answer "bdace" will never come even though it is a correct order. In case of using BFS, "bedac" will come and in case of DFS it will be "ebdac", since you are pushing 'e' at the end in the stack after checking that all other alphabets are already visited.
Understood 👍
Best Explaination.cpp
Why not compare all pairs of strings but pick only the i and i - 1?
I didn't find it intuitive
Becoz it is already sorted in ques. In dictionary you can compare next two to get the idea which comes first
understood 100% 😍
understood:)
superb man
What if we keep nodes as 'a' 'b' 'c' and so on instead of converting them to a number?
You can, it will just complicated for lookup. You may then have to use Hash map to look for that character over vector or list. Its just easy indexing with sequential numbers