568. Verifying an Alien Dictionary
An alien language uses the same 26 lowercase letters as English, but ranks them in its own sequence. You get words, a list of words written in that language, and order, a 26-character string that lists every lowercase letter exactly once from smallest rank to largest.
Return true if words is already sorted (non-decreasing) under the alien ranking, and false otherwise.
Two words compare exactly like dictionary entries, just with the alien ranking in place of a–z: scan both words from the left, and the first position where they disagree decides which word is smaller. If one word runs out before any position disagrees, it is a prefix of the other and must come first — so "app" before "apple" is fine, but "apple" before "app" is not.
Example 1:
Input: words = ["hat", "lab", "lot"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output: true
Explanation: Under this ranking h comes before l, so "hat" < "lab". Then "lab" and "lot" first differ at position 1, where a (rank 2) comes before o — the list is sorted.
Example 2:
Input: words = ["apple", "app"], order = "abcdefghijklmnopqrstuvwxyz"
Output: false
Explanation: "app" is a prefix of "apple", so it must appear first. Here the longer word comes first, which breaks dictionary order.
Constraints:
- 1 ≤ words.length ≤ 100
- 1 ≤ words[i].length ≤ 20
- order.length == 26
- Every character in words[i] and order is a lowercase English letter.
- order contains each of the 26 letters exactly once.
Hints:
A list is sorted exactly when every ADJACENT pair is in order — you never need to compare non-neighboring words.
Comparing two words needs each letter's rank. order.index(c) works but rescans the string every call; build a map/array from letter → position once, then every lookup is O(1).
Watch the tie case: if the loop over shared positions finds no difference, the shorter word must be the earlier one.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: words = ["hat", "lab", "lot"], order = "hlabcdefgijkmnopqrstuvwxyz"
Expected output: true