Awesome solution!! Makes it much more clean the way you stored w1,w2 as a variable
@sirpavr3182
3 жыл бұрын
would be great if you could discuss the complexity on your videos.
@amankassahunwassie587
Жыл бұрын
How this is a graph problem?
@OfficialZushi
4 ай бұрын
My guess is that you can make a prefix Tree by graphing each word. Then the validation algorithm would be traversing the tree. Might be better when there's a large amount of words, but idrk
@sproutboot
2 жыл бұрын
I had a hard time understand the question, thank you. for the first 2~3min I had a good understanding of the problem
@aryamankukal1056
3 жыл бұрын
8:58 why don't you have to continue when you found the first differing char?
@asdasddas100
3 жыл бұрын
Because if I give you two strings: "Apple" "Banana" You only need to compare the first character to know that Apple comes first. You only need to continue if the first character is the same and continue character by character
@danielsun716
Жыл бұрын
a little tricky thing is this solution does not use minLen of w1 and w2. But that is an excellent trick to solve the pre-work.
@expertium2255
Жыл бұрын
After checking solutions on leetcode I found a much shorter and much more readable one: def isAlienSorted(self, words: List[str], order: str) -> bool: return words == sorted(words, key=lambda word:[order.index(c) for c in word]) Though people in the comments say that the interviewer would not allow this (I don't know why, I'm a beginner btw).
@amandatao9622
2 жыл бұрын
Thanks!
@director8656
3 жыл бұрын
Great Video as usual, thank you!
@jonaskhanwald566
3 жыл бұрын
Please do some videos on pattern matching (KMP algorithm)
@edwardteach2
2 жыл бұрын
U an Alien God
@kirillzlobin7135
2 ай бұрын
Amazing solution
@the-tech-jerry
9 ай бұрын
I still wonder why this question is in graph section of your road map.
@anupamkolay193
Жыл бұрын
Best Explanation possible.
@asadbekshomurodov8416
Жыл бұрын
Bro this solution just perfect !!!
@abhinavgupta7048
9 ай бұрын
Its complexity is O(N*26), am I right?
@xijinping5064
11 ай бұрын
I did this in Go, turns out not using a hashmap is faster because the order string is just 26 bytes lol
@MP-ny3ep
Жыл бұрын
Thank you , awesome explanation.
@yang5843
Жыл бұрын
This code is so well written
@krateskim4169
Жыл бұрын
Awesome explanation
@JJ-qv8co
3 жыл бұрын
is there anything better than O(n2) ?
@sk_4142
Жыл бұрын
bro, i think you put this problem in the wrong category on your website. don't think it belongs in the graphs section!
@amrholo4445
2 жыл бұрын
Thanks a lot sir
@superpupernone
5 ай бұрын
I didn't get it: why this problem in Graphs?!
@maamounhajnajeeb209
Жыл бұрын
thanks
@aa10259
Жыл бұрын
What's the use of the "break" ?
@trueknowledge1981
Жыл бұрын
if it hits that case where your chars are not equal and by alien dict it comes first which falsy, we should not any of further chars, to stop there we use break statement
@KrishnaSingh-yc7wp
Жыл бұрын
@@trueknowledge1981 didn't got u
@barissimsek
7 ай бұрын
When you find the first different char you don't need to go further. Because that different character (the most significant different) will define the order in the dictionary. Like Ape and Apple. 3rd chars are 'e' and 'p'. This information will define the order. Rest of the chars doesn't matter. Hence break.
@MiravMehtaishere
3 жыл бұрын
Is the time complexity , O(N-sqaured) ?
@jamsrandorjbatbayar3652
3 жыл бұрын
It is just O(N)
@aryamankukal1056
3 жыл бұрын
should be O(N+M) but it's 0(N) because the letters aren't infinite, there's just 26
@xjlonelystar
2 жыл бұрын
can't even solve an ez question -- cry in silence --
@mageshyt2550
Жыл бұрын
class Solution: def isAlienSorted(self, words, order: str) -> bool: order_list = {order[i]: i for i in range(len(order))} def helper(word1, word2): # check if word1 is lexicographically smaller than word2 for i in range(min(len(word1), len(word2))): if order_list[word1[i]] < order_list[word2[i]]: return True elif order_list[word1[i]] > order_list[word2[i]]: return False # if same prefix, check length return True if len(word1) < len(word2) else False for i in range(len(words)-1): # if same word , continue if words[i] == words[i+1]: continue if not helper(words[i], words[i+1]): return False return True
Пікірлер: 39