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
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
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).
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
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.
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
Alien Dictionary (HARD) - czcams.com/video/6kTZYvNNyps/video.html
Awesome solution!! Makes it much more clean the way you stored w1,w2 as a variable
I had a hard time understand the question, thank you. for the first 2~3min I had a good understanding of the problem
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.
Please do some videos on pattern matching (KMP algorithm)
would be great if you could discuss the complexity on your videos.
Great Video as usual, thank you!
How this is a graph problem?
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
8:58 why don't you have to continue when you found the first differing char?
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
Thank you , awesome explanation.
Best Explanation possible.
Thanks!
is there anything better than O(n2) ?
Bro this solution just perfect !!!
Its complexity is O(N*26), am I right?
This code is so well written
I still wonder why this question is in graph section of your road map.
Awesome explanation
I did this in Go, turns out not using a hashmap is faster because the order string is just 26 bytes lol
Amazing solution
Thanks a lot sir
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).
U an Alien God
What's the use of the "break" ?
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
@@trueknowledge1981 didn't got u
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.
thanks
Is the time complexity , O(N-sqaured) ?
It is just O(N)
should be O(N+M) but it's 0(N) because the letters aren't infinite, there's just 26
bro, i think you put this problem in the wrong category on your website. don't think it belongs in the graphs section!
I didn't get it: why this problem in Graphs?!
can't even solve an ez question -- cry in silence --
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
Thanks!
Thank you so much!