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

Since for three numbers , if
and
, then
; lexicographic order is transitive. Validating pairs of consecutive words is thus sufficient.
With words, alphabet size
, and the biggest word-length
, time:
and space:
.
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