Why do we need a heap here instead of queue?
if count != 0:
return None
return res
Why do we need this extra check? Can you explain with a test case?
“Keep in mind instead of using a regular queue, we need to use a heap to guarantee the smallest ordering.”
I think we should not use a minHeap to store nodes since after insertion the heap may contain nodes at 2 different levels and in heap re-ordering
might take place which may cause the node of a later level to be processed before node of previous level
Example: aaa abb abm azb yay yak
Here output should be “abykmz” but since we use heap output is “abmykz”
Please Correct me if i am wrong
Let’s say we take [aaa, abb, abm, azb, yay, yak] then the output should be “abykmz” but bcuz we use a heap we get “abmykz” which is wrong
I think this happens bcuz after inserting a node heap may contain node of 2 different levels and reordering might occur after insertion which
may cause the node of a later level to be processed before a node of a earlier level
Why is x > z?
Shouldn’t test#4 output be “abdfinrtclsp” instead of “abdfilnrtcsp” for input “stdlib stl scanf sscanf printf”?
From input,
d < l,
t < c < s,
s < p
So the first set of characters which have no parent are “abdfinrt”.
The output should be correct.
I finally understand it. From your example, the order is a < b < m, b < z, a < y < k. So “abmykz” actually meets all the conditions and is the smallest. The order of character is not determined by how many parents a character has.
someone please explain how a heap guarantees min ordering. i read below and am not getting it. wouldn’t min heappop return smallest element lexicographically in our own language, not alien one
wouldn’t heap return smallest ordering in our own language, not the alien one?
The heap is only used to satisfy requirement #4 in the description. The topological ordering is from Khan’s algorithm.
For testcase # 3:
Words: she sell seashell seashore seahorse on a
Solution: lnrsheoa
Comparing “seahorse” to “on” just gets us ‘s’ comes before o
and comparing “on” to “a” just gets us ‘o’ comes before ‘a’
How do we get information about the ‘n’ character
i think the graph created here has a cycle
she → sell gives us e → l
seashore → seashell gives us e → l
there is no topological ordering if there is a cycle in the graph
i think the graph created here has a cycle
she → sell gives us e → l
seashore → seashell gives us e → l
there is no topological ordering if there is a cycle in the graph
she → sell gives us e → l
– No, [s]he → [s]ell gives us h → e
seashore → seashell gives us e → l
– no, [seash]ore → [seash]ell gives us o → e
Look at the first character of each word that is different, I put the ones that are the same in brackets
she → sell gives us e → l
– No, [s]he → [s]ell gives us h → e
seashore → seashell gives us e → l
– no, [seash]ore → [seash]ell gives us o → e
Look at the first character of each word that is different, I put the ones that are the same in brackets
because we want to ensure that all letters are present in the answer,
if some letter had an “unresolved” dependency then it would never be added to heap, hence it would not be included in the ordergin
However, a faster way to check this requirement is to check for: len(res) != len(graph)
Would be nice if your test cases could validate all correct responses so I don’t have to copy/paste to leetcode and verify test cases failed here.