Alien Dictionary - Topological Sort - Leetcode 269 - Python
Вставка
- Опубліковано 30 чер 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
Problem Link: neetcode.io/problems/foreign-...
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
0:00 - Read the problem
4:46 - Drawing Explanation
15:46 - Coding Explanation
leetcode 269
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#topological #sort #python - Наука та технологія
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
wish the python solutions you just wrote would be on your site as well (:
Definitely it is helping me, Thanks a lot man!
Man if I get this question during an interview, ima just start looking for another interview.
for real. first of all, this level of difficulty is just unnecessary
Unfortunately it's very common in interviews especially at Airbnb
This is a catch, if you manage to solve this in interview, you will be put almost ahead of many other candidates. If you can't its just a bad day :)
You could also build the dependency in reverse order so you don't have do the reverse at the end. E.g., rather than a->c, do c->a
For those looking for the solution that also works in Lintcode, when iterating over the characters to call DFS on each one, we can replace:
`for char in adj:`
with:
`for char in reversed(sorted(adjacencyMap.keys())):`
This is because our solution already works for all connected components, but when we have 2 connected components, we want to ensure that we sort the start of our connected components by Human dictionary order (because Lintcode requires it). The reason we're sorting in reverse order, ex: z before a, is that we're going to reverse the result later on. Was looking for a while on how to convert Neetcode's solution to work with Lintcode's requirements and couldn't find it anywhere so figured I'd share the solution once I got it working.
Amazing, this works thank you
thanks
The postorder explanation was really mind blowing. I thought you would do it the traditional way by keeping incoming edge counts.
I can't wait when someday my client will request to implement this algorithm so they can sell the product to Alien.
one of the best part of your video is reading question. It is much clear after your explanation!
Been following Neetcode blind 75 playlist and Solved all the questions today. This was my last question. Looking forward to solve neetcode 150.
I am from tier 3 college and tier 3 branch of IT from India. Resources you provided give me hope that I could crack a job interview.
Just wanted to write a quick thank you. And show you how your efforts are having an impact on students coming from a small village in India.
Awesome stuff! Your videos are the reason I pass any interview at all.
Just another optimization, instead of reversing you can also store the result in a deque and insert at the front. It saves one traversal.
In Python, inserting an element at the front of a standard list (which behaves like an array) has a time complexity of O(n), where n is the number of elements currently in the list.
Here's why:
Python lists are implemented using arrays.
Inserting at the front requires shifting all existing elements one position to the right to make space for the new element.
Shifting n elements takes about n operations
that's why a deque was suggested: inserting is O(1) at front
Requesting dungean game and cherry pickup as well! Thanks for the awesome explanation as always.
How did I not find your channel before, awesome explanation!
Brilliant solution, Enjoyed the explanation!
Kahn's algorithm can be implemented to find Topological order in a DAG.
yes, kahn;s method is simple to understand
any examples sir, please.
any examples sir, please.
any examples sir, please.
any example sir, please.
Very well explained! Thanks a ton for these videos. Appreciate it.
Thank you so much for such beautiful explanations....just wanted to point out that probably dfs function's last line should be return false coz it didn't find the cycle (though in python it won't matter as default will be None) but worth mentioning.Please correct me if I am wrong.
Thanks...you are awesome!!!
U are right.
I think the lintcode version of this question is different and it's failing tests. Eg:
Input
["ab","adc"]
Output
"cbda"
Expected
"abcd"
Here is a working JS solution for the lintcode problem in JavaScript.. it wasn't easy!
/**
* @param words: a list of words
* @return: a string which is correct order
*/
alienOrder(words) {
const adj = {};
const visiting = {};
const result = [];
for (const word of words) {
for (const letter of word) adj[letter] = adj[letter] || new Set();
}
for (let i = 1; i < words.length; i++) {
const word = words[i-1];
const nextWord = words[i];
if (word.startsWith(nextWord)) return '';
for (let j = 0; j < nextWord.length; j++) {
const first = word[j];
const last = nextWord[j];
if (first !== last) {
if (first !== undefined) adj[first].add(last);
break;
}
}
}
for (const char of Object.keys(adj).sort().reverse()) {
if (dfs(char)) return ''
}
return result.reverse().join('');
function dfs(char) { // Return true if we have an invalid graph, cycle
if (visiting[char]) return true; // Cycle detected
if (char in visiting) return; // Already visited
visiting[char] = true;
for (const successor of adj[char]) {
if (dfs(successor)) return true;
}
visiting[char] = false;
result.push(char);
}
}
yes, how do you find the right one when there's multiple possibilities?
Got asked this in a Facebook interview. Needless to say I failed
Right on, traveler.
Damn. You were passing interview to Senior SDE position, I guess?
@@StanisLoveSidno lol, this was for an intern spot
@@rodgerdodger17 bloody hell
@@StanisLoveSid It works the other way around. Senior positions need strong System Design and Behavioral.
Do we always go with post-order traverse for DAG and reverse the result? Not sure if my professor ever mentioned this. lol
Thanks for the explanation. You can make 'res' a deque() type and use appendleft(), thereby avoiding the need to reverse the result towards the end.
Also, your solution needs a small fix to work for all test cases in leetcode.
The loop through in line 29, should be for all unique characters in the 'words' parameter and not all keys in the 'adj' dict. This modification handles scenarios like when input is ['z', 'z'].
Great explanation my friend! I appreciate it!
Done thanks
6:20 you only need to compare words to the word right after it and not to every other word in the list because the list itself is sorted lexicographically according to the language
Just found about your channel, your work is awesome 🔥🔥🔥🔥. Can you make some new playlists on the basis of questions asked by each companies.
Like all these were asked by Facebook or microsoft
Very well explained solution of a hard problem. The explanation of contradiction solution and DFS explanation is very good :)
I couldnt solve it on leetcode for its worst explanation, then i find out your video watch your explanation after that it dosent seems that much hard now. Thanks neetcode keep up the good work
Great solution! I think the difficult part is to understand the problem and build up the adj list. After that the problem basically Course Schedule I or Course Schedule II (topological sort or graph coloring will works) :). Thanks for the explaination
Just got asked a very similar question in an interview, didn't remember the topo sort at all but somehow managed to do it using a dictionary with letter : unique_letters_after and then
1. Getting out a letter which doesn't appear in the dict values (ie. doesn't appear after any other letter)
2. Removing it from the dictionary
3. Repeat until dict is empty, and at this point you just have to append the last letter, which is a letter that doesn't appear in the dictionary keys
Good solution. But I think it may fail in test cases like ["ab","abc"] in LintCode where we are expected to return abc as the solution, but as per this logic we are only concerned about ordering in w1 and w2 and hence this solution considers cba as the right answer. Need more clarity on this part.
actually no , there is no order could tell in this test case. Let say we have ["can","cancel"] in English, but instead of "canel" , We all know "aceln" is the correct order in English. But we wouldn't know it if we can't compare in Alien Language. So any order could be the answer. I hope this help your cunfuse.
The question on lint code is slightly different from the question on leetcode. Leetcode says return in any order if multiple solutions exist. Lint code asks to return in human lexicographical order if multiple solutions exist.
Excellent explanation. Awesome channel . Thanks !!!!
If your code fails to pass Leetcode testcases just add these two if statements before building adj dictionary:
if not words: return ""
if len(set(words)) == 1:
return "".join(set(c for c in words[0]))
This is needed due to test cases like ["z", "z"], or ["aba"]
Cases will still fail for inputs like "ab","abc"
Very nice explantion. Thank you!
LincCode further specifies when it's a tie:
4. There may be multiple valid order of letters, return the smallest in normal lexicographical order.
5. The letters in one string are of the same rank by default and are sorted in Human dictionary order.
I did the lintcode version. I started with the strategy used in in CourseSchedule II. I also used two sets putting all the letters in both (noPre, noPost). Then I removed elements from noPre if a letter had a preceding letter and removed from noPost if a letter had post letter.
I combined the noPre and noPost to form a startOrEnd set. Think of it as ends of a rope\thread. I created a list from the startOrEnd set. Sorted the list in lexicographical order. Then did dfs for each letter in the startOrEnd list. I deleted an element from the adjacency list when all it's preceding elements had been processed successfully. If the adjacency list was not empty after processing everything in the startOrEnd list then the input had a loop and a blank string was returned. There was a loop check in the dfs as well.
Adding all the unique characters in the words to the adjacency list would help in resolving all the edge cases.
posting this just in case it helps anyone like me who struggled with the intuition of why we need post-order (instead of pre-order) traversal. so I kept thinking, "either way it guarantees that the current char will end up in front of all its children, so what the heck is the difference?". the magic moment was when I realized post-order is like doing everything from the _back_ of the line, so any of its parents we haven't processed yet are still free to end up in front of it. pre-order on the other hand doesn't leave any room for them, since it already starts from the front
for some reason imagining people going to the back of an imaginary line helped
@NeetCode, can you check updated description for this problem, given the description isn't it too hard to be asked in an interview, but has been asked a lot of times
Please update the c++ code for this problem on neetcode website.
Outer for loop from inDegree initialisation is misplaced.
Also neetcode compiler is giving, g++ internal compiler out of space error.
Thank you. You are doing god's work. 🙏🏻
Quick question: why do you only have to compare every word to the word to its right? Wouldn't there be additional relationships between the first and the fifth word for example. How can you know for sure you aren't missing any relationships by just looking at every adjacent pair of words?
Since we know the words are already in sorted order.
A simple example would be [a, b, c]. Here we know b comes after a (a -> b) and that c comes after b (b -> c).
This tells us a -> b -> c. So it makes no sense to compare a and c.
@@NeetCode Perfect makes sense. Thank you!
I was also confused with the same doubt.
Consider these test cases:
a, bc, bd, ba
a, bc, bd, bde, ed
So, what I understood, if we try to create a test case to break the above assumption, either we end up creating a cycle or the order is preserved and maybe there are some extra edges added if we do for all the pairs.
Bro this was the answer I was keep looking for, I'm used to implement topological sort using post order BFS and there are bunch of soln out there which use some other technique like inorder to implement topological sort which I don't know. Thanks Man!
If you're doing this on Lintcode, there's an extra requirement to return the soln in English lex order if there is more than one soln.
to that end, just run the dfs on the keys in the adjacency in reverse... in a list (since we didn't use ordereddict)
for c in sorted([c for c in adj.keys()], reverse=True):
if dfs(c): return ''
adj is my adjacency dict.
then everything else can stay the same (including the reverse sort before return)
Wow, thank you so much! I was really struggling with the issue, and your solution to it is beautiful
Great explanation!!
good explanation!
post order part is similar to reconstruct itinerary, like finding euler path (hierholzer's algoritm)
Thanks for post order dfs, even though Bfs is easier in this question.
Thanks for sharing this great approach. I have a question regarding this problem.
If we pass in this input, ["zx","zy"], the expected output is "xyz". My question is, how are we able to determine that z comes after x and y?
Thinking about an example alphabetically it can be either before or after which is why I think this input should ideally return invalid as shown below. Let me know your thoughts. Thanks again.
["ad", "af"] --> adf
["zd", "zf] --> dfz
I am facing the same issue. Were you able to figure this out?
you are wayy too awesome!!
Instead of doing a reverse order, what if we change the direction of edges in our graph? Like similar to course schedule, adding the graph[w2[j]] = w1[j] kind of meaning like a dependency? Then we would be building it in correct order with post order DFS?
Nice Explanation, but i have one question in DFS method, for visit array why we are making True before False.
So that when we call dfs on its neighbors we can detect if a cycle is found by visiting this node again. Once we have checked all the neighbors we know we havent found a cycle so we can set it back to false to remove it from the path of nodes we are checking
Would the code pass the test case like ["x", "x"] and the case ["zy","zx"]?
Why didnt we check if the character is already in the result as a base case for dfs alongside the visited check? Normally we do topological sort like this.
Thank you for this.
I was confused because why didn't we use this method for the course schedule topological sort? we cleared the array once we are done with that. Can we use the same technique here?
i think you should be able to apply this to the course schedule.
Excellent video, thank you. One question: list like "abc", "ab" is not sorted lexicographically, right? The premise is "You are given a list of strings words from the alien language's dictionary, where the strings in words are sorted lexicographically by the rules of this new language." So, the input must be sorted lexicographically. List like "abc", "ab" should not appear in input. Why should we check "if len(w1) > len(w2) and w1[:minLen] == w2[:minLen]:" ? This should never happen, right?
Could you give some testcases where null string is returned? I cannot seem to wrap my head around the false cases.
i couldn't understand the question lol thanks for another great explanation!
How does this work for case ["a","ab"]? This creates and adj list of {a:{} , b:{}}
I might be missing something but looping through each node in adj list without some sort of order could have the result return an answer of [a,b] or [b,a].
Yes, it doesn't pass that test for me too.
Another failing test: ["ab","adc"] returns "cbda", while it should be "abcd"
@@capooti Aren’t “cbda” and “abcd” both valid results for the input [“ab”, “adc”]. The only information [“ab”, “adc”] provides is ‘b’ is somewhere before ‘d’ in the alphabet. Therefore, any result that places ‘b’ somewhere before ‘d’ (and contains all characters found in the provided words) is correct.
@@capooti Should be "abdc" you mean
AB
ADC
A -> B -> D -> C
since lintcode is adding another condition which is if there is multiple valid ordering of the letters then you should return the order with the smallest in lexographical order, i am not sure exactly how to implement it but i think if you were able to force the dfs to run on the letters backward it will work somehow
you could use these lines instead of the lines written at 29 and it will return the values in normal lexographical order as stated in lintcode, i tried it out
for c in sorted(adj.keys(),reverse=True):
if dfs(c):
return ""
When we construct a DAG from the input, we may end up with several independent connected components, where each connected component is a single vertex, or a directed sequence of vertices. Within each connected component, for any directed edge, the source vertex is smaller than the sink vertex. However, between the vertices of two connected components, there's no lexicographic relationship, since there isn't an edge between any vertex in either of those two components. In that case, the ordering between vertices of those two components are the same as normal 'human' ordering. This means that when we do the topological sort on keys of the DAG (if you represent the adjacency list as a Map), we need to consider vertices in the 'human' ordering. This ensures that the final result is composed of vertices that, WITHIN their connected components, are ordered in the 'alien' way, but are ordered in the 'human' way ACROSS connected components.
The LeetCode problem states that you can return the ANY valid solution. So you don't need 'human' order across connected components.
I see some people are talking about Lintcode having a different problem statement. If that's what you're referring to then you should say so.
You said we are looping through all the characters because we are doing this in reverse order. I understand how we are doing that as explained in the video (using dfs with post order). The algo works, but I am not understanding how since we loop through all the characters how are we not appending repeated characters?
neetcode has implemented top sort in course schedule 2, that template is easier to implement. Try that out..
@NeetCode, hello. Thanks for the sharing. I got one more question. The problem said "If there are multiple solutions, return any of them", what about return only the one as the earth english order like abcdefg...? what should we need to do?
Watching the video, I had a 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?
for the prefix check, is leetcode the same as lintcode where: The dictionary is invalid, if string a is prefix of string b and b is appear before a.
and can string a and b appear anywhere in words i.e. [a, ........, b] so a pairwise check for len(w1) > len(w2) and w1[:minLen] == w2[:minLen] is insufficient as you need to check every word with every other?
At 12:40 we could have gone to node B first also. Then it would have been BCA which, if u reverse it, is ACB which is incorrect. Right?
We cannot process B yet as it has a child C, which is unvisited. So no matter if we go to B or C from A, we still get CBA and reversing will give ABC
Watched this video 10 days ago. And try to redo it now and already forgot some of the details.
Nice solution, topological sort using DFS is slightly not clear to me. Do you have a video specifically explaining too sort using DFS?
After watching your explanation, I feel like a big dumb dumb for not thinking to model this as a graph
this is so clever
why do we only have to compare "adjacent words" when finding dependencies?
why cant we make the same dependencies from 1st and 3rd node
then 1st and 4th node
and so on...
anyone have the complexity of this ?
I think it's O(N*M) + O(K+E)
with:
N : number of words
M : max length of words
K : number of node
E : number of edge
Great explanation!! Thanks a lot :)
What about this test case ?
{"bac", "bad", "baefgh"}
graph will look like : c -> d -> e
and the topo sort is : c, d, e
But where is f, g, h in the order ????
HELP PLEASE !
can you please explain stone game showing min max algo?
Why is there a need for visited to have a false or true value? Can't we just check if the key exists and return false? What's the difference between visited and in path?
the nodes in `visited` are nodes that have ever been touched/visited. The nodes in `path` are nodes that are currently being visited in the recursion stack path.
BFS seemed more intuitive here for me
why don't you return anything at the end of the dfs method?
Why just the next word in graph construction and not all succeeding words?
Line 6. w2 should be from i to len(words) -1, right?
At 17:08, why does line 8 need `len(w1) > len(w2)`?
For anyone else that comes across this:
I believe the answer is because the absence of a character is considered lexicographically *lower* than the presence of any character.
If `len(w1) > len(w2) and w1[:minLen] == w2[:minLen]` then the first word is larger than the second AND the second word is a substring of the first word, yielding an invalid input and no solution (see 4:10).
Anyone know what time/space complexity this is mind sharing? I'm confident my idea isn't correct. Thanks!
15:31 he said it's the number of characters in the input for time and i think it's the same for space too :))
Please do more graph problems
U an Alien God. Setting the visit[c] = True and then to visit[c] = False, seems like a backtracking situation. But it isn't. Since our visit[c] was not set to False initially.
How can I even think of all the details of hard problem under 30-40min
Hi, for input [a,ab], ur code will give out "ba" but the answer is "ab", could explain a bit plz?
Hard became Easy for me after watching this
And how can I develop solution in under 30min in real faang interview?!!! This is. So hard
Is there any way to create a Lintcode account without Wechat? Can someone with a wechat account help me activate it
This is too hard for me now😶🌫
please do 729, accounts merge
👏👏
In a topological sort, evaluate the node that has no incoming edges first.
Fails for [“z”, “z”]
would changing the if check in line 8 to >= solve this ? I would say this is an invalid test case or a cycle probably.
You can fix this by making following modification:
- In line 29, loop through all unique characters found in the 'words' list
all_chars = set()
for word in words:
for char in word:
all_chars.add(char)
for char in all_chars:
if dfs(char):
return ""
3:10
this code in c++, anyone?
Why didn't you just say post DFS order is only about topological sorted order!!
this can also be represented with emoji's instead of alphanumeric characters such as the following:
1. 🧠❤🚀 🧠
2. 🧠❤ 🧠 🚀
3. 🧠❤ 🧠 🚀 🧠
4. ❤🚀
when he said this was intuitive, he was lying.
The alien should be scared
bfs is actually more intuitive and cleaner:
```
class Solution:
def alienOrder(self, words: List[str]) -> str:
adj_list = collections.defaultdict(set)
in_degree = Counter({c:0 for word in words for c in word})
for i in range(len(words)-1):
word = words[i]
next_word = words[i+1]
for char1, char2 in zip(word, next_word):
if char1 != char2:
if char2 not in adj_list[char1]:
adj_list[char1].add(char2)
in_degree[char2] += 1
break
else:
if len(next_word) < len(word):
return ""
queue = collections.deque([c for c in in_degree if in_degree[c] == 0])
output = []
while queue:
char = queue.popleft()
output.append(char)
for d in adj_list[char]:
in_degree[d] -= 1
if in_degree[d] == 0:
queue.append(d)
if len(output) < len(in_degree):
return ""
return "".join(output)
```
the explanation is wrong, for example for the test case
["wrt","wrf"]
the expected output is
"rtfw"
This means that only the first character and the length matter and the other chars do not, in the explanation he traverses the string like the other characters matter. I think this video is deprecated.
In the test case you provide, the only character of difference is the last one. So given the ordering, you can use any solution that has "t" before "f". For example, "rwtf" and "tfrw" will also pass that test case. It is a problem that may have multiple solutions like so.
is this meant for humans to solve.. .😭
I don't get how to solve this problem. I am fking stupid
you and me both
this is annoying, i hate this question !!
Making the adj list was the main challenge for me !But the list making is not exact i think! testcase fails ([zy],[zx]). PLease reply! Neetcode!
Its failing for me too. were you able to fix it ?