verifying_an_alien_dictionary

View Source

 1# @leet start
 2class Solution:
 3    def isAlienSorted(self, words: list[str], order: str) -> bool:
 4        """
 5        This question asks us to verify that the words provided are sorted according
 6        to an alien dictionary.
 7        We can do as the question asks, by sorting the words and making sure they
 8        align in $O(n log n)$ time.
 9
10        We can verify that words are properly sorted in $O(n)$ time, however.
11        If we zip the words and make sure that both words are in the right order
12        (l < r) for all words in the word list, the list is sorted.
13        """
14
15        dictionary = {c: i for i, c in enumerate(order)}
16
17        # This is the $O(n log n) solution
18        # return words == sorted(words, key=lambda word: [dictionary[c] for c in word])
19        for l, r in zip(words, words[1:]):
20            if [dictionary[c] for c in l] <= [dictionary[c] for c in r]:
21                continue
22            return False
23        return True
24
25
26# @leet end
27
28
29def test():
30    assert 2 + 2 == 4

class Solution: View Source

 3class Solution:
 4    def isAlienSorted(self, words: list[str], order: str) -> bool:
 5        """
 6        This question asks us to verify that the words provided are sorted according
 7        to an alien dictionary.
 8        We can do as the question asks, by sorting the words and making sure they
 9        align in $O(n log n)$ time.
10
11        We can verify that words are properly sorted in $O(n)$ time, however.
12        If we zip the words and make sure that both words are in the right order
13        (l < r) for all words in the word list, the list is sorted.
14        """
15
16        dictionary = {c: i for i, c in enumerate(order)}
17
18        # This is the $O(n log n) solution
19        # return words == sorted(words, key=lambda word: [dictionary[c] for c in word])
20        for l, r in zip(words, words[1:]):
21            if [dictionary[c] for c in l] <= [dictionary[c] for c in r]:
22                continue
23            return False
24        return True

def isAlienSorted(self, words: list[str], order: str) -> bool: View Source

 4    def isAlienSorted(self, words: list[str], order: str) -> bool:
 5        """
 6        This question asks us to verify that the words provided are sorted according
 7        to an alien dictionary.
 8        We can do as the question asks, by sorting the words and making sure they
 9        align in $O(n log n)$ time.
10
11        We can verify that words are properly sorted in $O(n)$ time, however.
12        If we zip the words and make sure that both words are in the right order
13        (l < r) for all words in the word list, the list is sorted.
14        """
15
16        dictionary = {c: i for i, c in enumerate(order)}
17
18        # This is the $O(n log n) solution
19        # return words == sorted(words, key=lambda word: [dictionary[c] for c in word])
20        for l, r in zip(words, words[1:]):
21            if [dictionary[c] for c in l] <= [dictionary[c] for c in r]:
22                continue
23            return False
24        return True

This question asks us to verify that the words provided are sorted according to an alien dictionary. We can do as the question asks, by sorting the words and making sure they align in $O(n log n)$ time.

We can verify that words are properly sorted in $O(n)$ time, however. If we zip the words and make sure that both words are in the right order (l < r) for all words in the word list, the list is sorted.

def test(): View Source

30def test():
31    assert 2 + 2 == 4