Verify Lexicographic Order with Custom Alphabet

Problem

Given a series of words written using a scrambled alphabet, determine whether the list of strings is lexicographically sorted in ascending order.

You are given a list of N words and the alphabet order as a sorted array of characters. The first character in the alphabet array has the lowest rank, the second has the next lowest, and so on.

Examples

Example 1:

` Input: words = ["cat", "bat", "tab"] alphabet = ['c','b','a','t']

Output: True

Explanation: In this alphabet, the order is c < b < a < t. Comparing "cat" and "bat": first characters are 'c' and 'b'. Since c < b in this alphabet, "cat" < "bat". Correct order. Comparing "bat" and "tab": first characters are 'b' and 't'. Since b < t in this alphabet, "bat" < "tab". Correct order. `

Example 2:

` Input: words = ["hello", "world"] alphabet = ['w','o','r','l','d','h','e']

Output: False

Explanation: In this alphabet, w < h, so "world" < "hello". The list is not in ascending order. `

Requirements

1. Build a mapping from each character to its position (rank) in the custom alphabet
2. Compare adjacent words pairwise using the custom ordering
3. For each pair, compare character by character using the custom ranks
4. Handle prefix cases: if one word is a prefix of another, the shorter word should come first

Constraints

• 1 <= words.length <= 100
• 1 <= words[i].length <= 20
• All characters in words appear in alphabet
• alphabet contains unique characters

Hint 1: Building the Order Map Create a dictionary that maps each character to its index in the alphabet array. This gives you O(1) lookup for character comparison: order = {char: i for i, char in enumerate(alphabet)}

Hint 2: Comparing Two Words Compare two words character by character. If characters differ, use the order map to determine which comes first. If one word is a prefix of the other, the shorter word should come first.

Full Solution ` from typing import List

def is_sorted(words: List[str], alphabet: List[str]) -> bool: order = {char: i for i, char in enumerate(alphabet)}

def compare(word1: str, word2: str) -> bool:
    """Return True if word1 <= word2 in custom alphabet order."""
    for c1, c2 in zip(word1, word2):
        if order[c1] < order[c2]:
            return True
        elif order[c1] > order[c2]:
            return False
    # One is a prefix of the other -- shorter should come first
    return len(word1) <= len(word2)

for i in range(len(words) - 1):
    if not compare(words[i], words[i + 1]):
        return False
return True

`

Time complexity: O(N * M) where N is the number of words and M is the average word length.

Space complexity: O(K) where K is the alphabet size for the order map.