Verify Lexicographic Sort With Custom Alphabet#

Levels: level-3

Data structures: string, hash-table

Patterns: hashing

Practice Link#

Description#

You are given:
- words: a list of lowercase words.
- order: a custom ordering of characters (e.g., ['c','b','a','t', ...]).
Return True if words is sorted lexicographically according to order, else return False.
Lexicographic rules:
- Compare characters left-to-right using the custom order.
- If all characters match up to the shorter length, the shorter word must come first.

Examples#

1Input:
2words = ["cat", "bat", "tab"]
3order = ['c', 'b', 'a', 't']
4Output: True

1Input:
2words = ["cat", "tab", "car"]
3order = ['a','b','c',...,'z']   (normal alphabet)
4Output: False

Python Solution#

 1from typing import Dict, List
 2
 3
 4def is_sorted_alien(words: List[str], order: List[str]) -> bool:
 5    """
 6    Returns True if `words` is sorted under the custom alphabet `order`.
 7
 8    Time:  O(total characters across comparisons) ~= O(sum(len(words[i])))
 9    Space: O(|alphabet|)
10    """
11    if not words:
12        return True
13
14    rank: Dict[str, int] = {ch: i for i, ch in enumerate(order)}
15
16    def in_correct_order(a: str, b: str) -> bool:
17        # Compare a vs b according to rank
18        i = 0
19        n, m = len(a), len(b)
20        while i < n and i < m:
21            ca, cb = a[i], b[i]
22            if ca != cb:
23                return rank[ca] < rank[cb]
24            i += 1
25        # All matched up to min length: shorter must come first
26        return n <= m
27
28    for i in range(len(words) - 1):
29        if not in_correct_order(words[i], words[i + 1]):
30            return False
31    return True