Verifying an Alien Dictionary | Easy

Leetcode

Intuition:

  • Store the alien alphabet in a dictionary so that lookup can be in O(1)

Gotchas

  • Not all characters need to be verified, only when the characters are equal
  • The words might not be of the same length

Base case:

  • at least two words to be given

Solution:

class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        order = { v:k for k,v in enumerate(order) }
        if len(words) < 2:
            return True
        i = 0
        j = 1
        def compareWords(w1, w2):
            i = 0
            j = 0
            while i < len(w1) and j < len(w2):
                if order[w1[i]] < order[w2[j]]:
                    return True
                elif order[w1[i]] > order[w2[j]]:
                    return False
                else:
                    i += 1
                    j += 1
            if len(w1) < len(w2):
                return True
            else:
                return False

        while j < len(words):
            if not compareWords(words[i], words[j]):
                return False
            i += 1
            j += 1
        return True

Complexity Analysis:

O(N) where N is the length of all characters in the word list

Comments

comments powered by Disqus