Alien Dictionary - Topological Sort - Leetcode 269 - Python

0:00 - Read the problem
4:46 - Drawing Explanation
15:46 - Coding Explanation

leetcode 269

#topological #sort #python

[yu-changcheng]

I can't wait when someday my client will request to implement this algorithm so they can sell the product to Alien.

[jerrykuo]

Man if I get this question during an interview, ima just start looking for another interview.

[TyzFix]

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

[harikuduva]

The postorder explanation was really mind blowing. I thought you would do it the traditional way by keeping incoming edge counts.

[bulioh]

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

[Allen-tueu]

one of the best part of your video is reading question. It is much clear after your explanation!

[guyhadas]

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

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.

[wervana]

Solved this on my own. I don't know if I should celebrate such a small achievement or not but hey, I am improving. Thanks NC, following your 150 sheet

[mostinho]

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

[musicalnerves]

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.

[sheikhmkrifat]

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

[unwanted_spam]

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.

[sanjeev]

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!!!

[rodgerdodger]

Got asked this in a Facebook interview. Needless to say I failed

[shahayush]

Found that the dfs part is very similar to the Course Schedule II solution. So modified it in the same way. The visited False and True is slightly confusing for me and difficult to remember.

class Solution:
def foreignDictionary(self, words: List[str]) -> str:
adj = {c: set() for w in words for c in w}
for i in range(len(words) - 1):
w1, w2 = words[i], words[i + 1]
minLen = min(len(w1), len(w2))
if len(w1) > len(w2) and w1[:minLen] == w2[:minLen]:
return ""
for j in range(minLen):
if w1[j] != w2[j]:
adj[w1[j]].add(w2[j])
break

visited = set()
path = set()
res = []

def dfs(c):
if c in visited:
return True
if c in path:
return False
path.add(c)
for nei in adj[c]:
if not dfs(nei):
return False
path.remove(c)
visited.add(c)
res.append(c)
return True

for c in adj:
if not dfs(c):
return ""

return "".join(res[::-1])

[clintondannolfo]

I think the lintcode version of this question is different and it's failing tests. Eg:
Input
["ab", "adc"]
Output
"cbda"

Expected
"abcd"

[username__]

Kahn's algorithm can be implemented to find Topological order in a DAG.

[MinhNguyen-lzpg]

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

[alekseilitvinau]

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"]

[vishyarjun]

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.