Verifying an Alien Dictionary - Leetcode 953 - Python

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

leetcode 953

#verify #dictionary #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[the-tech-jerry]

I still wonder why this question is in graph section of your road map.

[MIDNightPT]

Awesome solution!! Makes it much more clean the way you stored w1, w2 as a variable

[AmgadDeyaa]

Usually I don't need to see your code just after the Explanation I can code it with my self great channel

[sirpavr]

would be great if you could discuss the complexity on your videos.

[sproutboot]

I had a hard time understand the question, thank you. for the first 2~3min I had a good understanding of the problem

[aryamankukal]

8:58 why don't you have to continue when you found the first differing char?

[akhma]

This is very helpful, Neet. Thanks for all the work!

[danielsun]

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.

[jonaskhanwald]

Please do some videos on pattern matching (KMP algorithm)

[expertium]

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).

[sadekjn]

bro, i think you put this problem in the wrong category on your website. don't think it belongs in the graphs section!

[superpupernone]

I didn't get it: why this problem in Graphs?!

[xijinping]

I did this in Go, turns out not using a hashmap is faster because the order string is just 26 bytes lol

[aa]

What's the use of the "break" ?

[xjlonelystar]

can't even solve an ez question -- cry in silence --

[abhinavgupta]

Its complexity is O(N*26), am I right?

[MiravMehtaishere]

Is the time complexity, O(N-sqaured) ?

[mageshyt]

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