# LeetCode 953: Verifying an Alien Dictionary

## Problem Restatement

We are given:

1. A list of words called `words`
2. A string called `order`

The string `order` describes the alphabet order used in an alien language.

We need to check whether the words are sorted lexicographically according to this alien alphabet.

Return `true` if the list is correctly sorted. Otherwise, return `false`.

The official constraints are:

| Constraint | Value |
|---|---|
| `1 <= words.length <= 100` | Number of words |
| `1 <= words[i].length <= 20` | Word length |
| `order.length == 26` | Alien alphabet size |
| Characters | Lowercase English letters |

Source: LeetCode problem statement. ([leetcode.com](https://leetcode.com/problems/verifying-an-alien-dictionary/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | Array of strings `words` |
| Input | String `order` representing alien alphabet order |
| Output | `true` if words are sorted, otherwise `false` |

Example function shape:

```python
def isAlienSorted(words: list[str], order: str) -> bool:
    ...
```

## Examples

Example 1:

```python
words = ["hello", "leetcode"]
order = "hlabcdefgijkmnopqrstuvwxyz"
```

Output:

```python
True
```

Explanation:

The alien alphabet starts with:

```python
h < l < a < b < ...
```

Compare:

```python
"hello"
"leetcode"
```

The first different characters are:

```python
h and l
```

Since `h < l` in the alien order, the words are correctly sorted.

Example 2:

```python
words = ["word", "world", "row"]
order = "worldabcefghijkmnpqstuvxyz"
```

Output:

```python
False
```

Explanation:

Compare:

```python
"word"
"world"
```

The first different characters are:

```python
d and l
```

In the alien order:

```python
l comes before d
```

So `"word"` should appear after `"world"`.

Example 3:

```python
words = ["apple", "app"]
order = "abcdefghijklmnopqrstuvwxyz"
```

Output:

```python
False
```

Explanation:

The shorter word should come first when one word is a prefix of the other.

So:

```python
"app" < "apple"
```

But the list gives the reverse order.

## First Thought: Use Normal String Comparison

Python already supports string comparison:

```python
"abc" < "abd"
```

But Python uses the normal English alphabet order.

This problem uses a custom alphabet.

So we cannot compare characters directly.

Instead, we must map each character to its alien position.

## Key Insight

Lexicographical comparison works like dictionary comparison.

We compare two words character by character.

At the first position where they differ:

- the smaller character decides the smaller word
- later characters no longer matter

Example:

```python
abc
abd
```

The first difference is:

```python
c vs d
```

Since `c < d`, the first word is smaller.

We can simulate this by assigning each alien character a rank.

Example:

```python
order = "hlabcdefgijkmnopqrstuvwxyz"
```

Then:

```python
rank['h'] = 0
rank['l'] = 1
rank['a'] = 2
...
```

Now we can compare characters using numeric ranks.

## Algorithm

Create a dictionary:

```python
character -> alien rank
```

Then compare every adjacent pair of words.

For each pair:

1. Compare characters from left to right.
2. Stop at the first different character.
3. If the first word has a larger alien rank, return `False`.
4. If the first word has a smaller alien rank, the pair is valid.
5. If all compared characters are equal, the shorter word must come first.

If all adjacent pairs are valid, return `True`.

## Prefix Rule

This is the most important edge case.

Consider:

```python
"apple"
"app"
```

All compared characters match:

```python
a == a
p == p
p == p
```

Now one word ends.

In lexicographical ordering, the shorter word is smaller.

So:

```python
"app" < "apple"
```

Therefore:

```python
["apple", "app"]
```

is invalid.

## Correctness

We compare each adjacent pair of words because a list is sorted if and only if every adjacent pair is sorted.

For a pair of words, lexicographical order depends on the first position where the characters differ.

If at that position the first word has a character with larger alien rank, then the first word should appear later, so the ordering is invalid.

If the first word has a smaller alien rank, then the pair is correctly ordered, and later characters do not matter.

If all compared characters are equal, then one word is a prefix of the other. In lexicographical ordering, the shorter word must come first. Therefore, if the first word is longer than the second word while sharing the same prefix, the ordering is invalid.

The algorithm checks exactly these conditions for every adjacent pair. Therefore, it correctly determines whether the full list is sorted according to the alien alphabet.

## Complexity

Let:

```python
n = len(words)
m = average word length
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(n * m)` | Each character is compared at most once |
| Space | `O(1)` | The rank map stores only 26 letters |

The alphabet size is fixed, so the rank dictionary uses constant space.

## Implementation

```python
class Solution:
    def isAlienSorted(self, words: list[str], order: str) -> bool:
        rank = {
            char: index
            for index, char in enumerate(order)
        }

        for i in range(len(words) - 1):
            word1 = words[i]
            word2 = words[i + 1]

            min_length = min(len(word1), len(word2))

            found_difference = False

            for j in range(min_length):
                c1 = word1[j]
                c2 = word2[j]

                if c1 != c2:
                    if rank[c1] > rank[c2]:
                        return False

                    found_difference = True
                    break

            if not found_difference and len(word1) > len(word2):
                return False

        return True
```

## Code Explanation

We first build the alien rank mapping:

```python
rank = {
    char: index
    for index, char in enumerate(order)
}
```

Example:

```python
order = "hlabcdefgijkmnopqrstuvwxyz"
```

creates:

```python
rank['h'] = 0
rank['l'] = 1
rank['a'] = 2
...
```

Then we compare every adjacent pair:

```python
for i in range(len(words) - 1):
```

We extract the two current words:

```python
word1 = words[i]
word2 = words[i + 1]
```

We compare only up to the shorter length:

```python
min_length = min(len(word1), len(word2))
```

Inside the loop:

```python
if c1 != c2:
```

we found the first meaningful difference.

If the alien rank is reversed:

```python
if rank[c1] > rank[c2]:
    return False
```

then the list is not sorted.

Otherwise, this pair is valid, so we stop checking this pair:

```python
found_difference = True
break
```

After the loop, if no difference was found:

```python
if not found_difference and len(word1) > len(word2):
```

then one word is a prefix of the other.

If the first word is longer, the ordering is invalid.

If all pairs pass, we return:

```python
return True
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.isAlienSorted(
        ["hello", "leetcode"],
        "hlabcdefgijkmnopqrstuvwxyz"
    ) is True

    assert s.isAlienSorted(
        ["word", "world", "row"],
        "worldabcefghijkmnpqstuvxyz"
    ) is False

    assert s.isAlienSorted(
        ["apple", "app"],
        "abcdefghijklmnopqrstuvwxyz"
    ) is False

    assert s.isAlienSorted(
        ["app", "apple"],
        "abcdefghijklmnopqrstuvwxyz"
    ) is True

    assert s.isAlienSorted(
        ["z", "x"],
        "zyxwvutsrqponmlkjihgfedcba"
    ) is True

    assert s.isAlienSorted(
        ["kuvp", "q"],
        "ngxlkthsjuoqcpavbfdermiywz"
    ) is True

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Standard valid example | Basic alien ordering |
| Invalid order example | Wrong character ranking |
| Prefix failure | Longer word before prefix |
| Valid prefix order | Shorter prefix first |
| Reversed alphabet | Non-standard character ordering |
| Random alien alphabet | General correctness |