Problem statement

https://leetcode.com/problems/verifying-an-alien-dictionary/

Solution

If you solved problem Alien Dictionary already, this one will be just copy paste. However if you not, it is still very simple. The idea is to look at pairs of adjacent words and look for first different symbol, for example hello and help means, that o shold go before p. Also we need to deal with cases like hello and hell, where the first one never can go before the second, so we return False in this case.

Complexity

It is just O(m), where m is the total length of all words in words.

Code

class Solution:
    def isAlienSorted(self, words, order):
        ord_d = {l:i for i, l in enumerate(order)}
         
        for w1, w2 in zip(words, words[1:]):
            for i, j in zip(w1, w2):
                if i != j:
                    if ord_d[i] > ord_d[j]: return False
                    break
            if w1.startswith(w2) and w1 != w2: return False
            
        return True