Validate Sorted Order Under a Custom Alphabet
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
A distant colony uses the same 26 lowercase English letters as we do, but their alphabet is arranged in a different order. You are given that ordering as a string `order` — a permutation of all 26 lowercase letters — where the position of a letter in `order` defines its rank (the first letter is the "smallest", the last is the "largest").
You are also given a list of words, `words`, where every word consists only of lowercase English letters. Determine whether `words` is sorted in non-decreasing lexicographic order **according to the colony's alphabet** (`order`), not the usual English alphabet.
Two words are compared the same way as in a normal dictionary, but using the custom letter ranks:
- Compare characters position by position. At the first position where the two words differ, the word whose character has the smaller rank in `order` comes first.
- If one word is a proper prefix of the other (all compared characters are equal and one word runs out of letters first), then the shorter word comes first.
Return `true` if the words are already in sorted order under this rule, and `false` otherwise.
### Examples
Example 1:
- `order = "hlabcdefgijkmnopqrstuvwxyz"`, `words = ["hello", "leetcode"]`
- Output: `true`
- Explanation: In this alphabet `'h'` has a smaller rank than `'l'`. Comparing the first characters of `"hello"` and `"leetcode"`, `'h'` comes before `'l'`, so the pair is in order.
Example 2:
- `order = "worldabcefghijkmnpqstuvxyz"`, `words = ["word", "world", "row"]`
- Output: `false`
- Explanation: In this alphabet `'w'` is rank 0, `'o'` is rank 1, `'r'` is rank 2, `'l'` is rank 3, and `'d'` is rank 4. Comparing `"word"` and `"world"`, the first three characters (`'w'`, `'o'`, `'r'`) match, then they differ at index 3: `'d'` (rank 4) in `"word"` versus `'l'` (rank 3) in `"world"`. Since `'l'` has the smaller rank, `"world"` should come before `"word"`, so this pair is out of order. (The second pair, `"world"` vs `"row"`, is fine: `'w'` has rank 0 and `'r'` has rank 2, so `"world"` correctly precedes `"row"`.) Because the first pair is out of order, the list is not sorted.
Example 3:
- `order = "abcdefghijklmnopqrstuvwxyz"` (standard order), `words = ["apple", "app"]`
- Output: `false`
- Explanation: `"app"` is a proper prefix of `"apple"`, so `"app"` must come first. Since `"apple"` appears before `"app"`, the list is not sorted.
### Constraints
- `1 <= words.length <= 100`
- `1 <= words[i].length <= 20`
- All characters in `words[i]` are lowercase English letters.
- `order.length == 26` and `order` is a permutation of all 26 lowercase English letters.
Aim for `O(N * L)` time, where `N` is the number of words and `L` is the maximum word length.
Quick Answer: This question evaluates a candidate's ability to apply custom ordering rules and string comparison logic, a common variant of array and string validation problems. It tests practical coding skill in mapping characters to an alternate rank system and handling edge cases like prefix relationships, commonly used to assess linear-time algorithm design.
You are given a string `order`, a permutation of all 26 lowercase English letters, that defines a custom alphabet: the position of a letter in `order` is its rank (index 0 is the smallest, index 25 the largest).
You are also given a list `words` of lowercase words. Determine whether `words` is sorted in non-decreasing lexicographic order according to this custom alphabet, using normal dictionary comparison rules but with the custom letter ranks:
- Compare characters position by position. At the first position where two adjacent words differ, the word whose character has the smaller rank in `order` must come first.
- If one word is a proper prefix of the other (all compared characters equal, one word runs out first), the shorter word must come first.
Return `true` if `words` is already sorted under this rule, `false` otherwise.
Example 1: order = "hlabcdefgijkmnopqrstuvwxyz", words = ["hello", "leetcode"] -> true ('h' outranks 'l').
Example 2: order = "worldabcefghijkmnpqstuvxyz", words = ["word", "world", "row"] -> false ("world" should precede "word").
Example 3: order = "abcdefghijklmnopqrstuvwxyz", words = ["apple", "app"] -> false ("app" is a proper prefix and must come first).
Aim for O(N * L) time, where N is the number of words and L is the maximum word length.
Constraints
- 1 <= words.length <= 100
- 1 <= words[i].length <= 20
- All characters in words[i] are lowercase English letters.
- order.length == 26 and order is a permutation of all 26 lowercase English letters.
Examples
Input: (["hello", "leetcode"], "hlabcdefgijkmnopqrstuvwxyz")
Expected Output: True
Explanation: 'h' has a smaller rank than 'l' in this alphabet, so "hello" correctly precedes "leetcode".
Input: (["word", "world", "row"], "worldabcefghijkmnpqstuvxyz")
Expected Output: False
Explanation: At index 3, 'd' (rank 4) vs 'l' (rank 3): "world" should come before "word", so the first pair is out of order.
Input: (["apple", "app"], "abcdefghijklmnopqrstuvwxyz")
Expected Output: False
Explanation: "app" is a proper prefix of "apple", so "app" must come first; it appears after, so the list is not sorted.
Input: (["app", "apple"], "abcdefghijklmnopqrstuvwxyz")
Expected Output: True
Explanation: The shorter prefix "app" correctly comes before "apple".
Input: (["a"], "abcdefghijklmnopqrstuvwxyz")
Expected Output: True
Explanation: A single word is trivially sorted.
Input: (["abc", "abc"], "abcdefghijklmnopqrstuvwxyz")
Expected Output: True
Explanation: Equal adjacent words satisfy non-decreasing order.
Input: (["zzz", "aaa"], "zyxwvutsrqponmlkjihgfedcba")
Expected Output: True
Explanation: Under a fully reversed alphabet, 'z' is the smallest letter, so "zzz" correctly precedes "aaa".
Hints
- Build a map from each letter to its index in `order` so you can look up any letter's rank in O(1).
- Only adjacent pairs of words matter: if every consecutive pair is in order, the whole list is sorted.
- To compare two words, scan characters together; at the first differing character compare their ranks. If no difference is found before one word ends, the shorter word must not come after the longer one (i.e. len(a) <= len(b)).