LeetCode 953: Verifying an Alien Dictionary

link

Lexicographic order between two words can be thought of as comparing two same-length numbers with the shorter one padded with 0‘s on the right.

Since for three numbers x, y, z, if x \le y and y \le z, then x \le z; lexicographic order is transitive. Validating pairs of consecutive words is thus sufficient.

With n words, alphabet size a, and the biggest word-length m, time: \mathcal{O}(m \cdot n) and space: \mathcal{O}(a).

class Solution:
    def is_lexicographically_before(self, curr_word: str, next_word: str, letter_pos: Dict[str, int]) -> bool:
        for u, v in zip(curr_word, next_word):
            if u == v:
                continue
            return letter_pos[u] < letter_pos[v]
        return len(curr_word) <= len(next_word) 

    def isAlienSorted(self, words: List[str], order: str) -> bool:
        letter_pos = { l : pos for pos, l in enumerate(order) }
        for i, curr_word in enumerate(words):
            # no next word to compare
            if i == len(words)-1:
                break
            next_word = words[i+1]
            if not self.is_lexicographically_before(curr_word, next_word, letter_pos):
                return False
        return True

Leave a comment