> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Verifying an Alien Dictionary Python Solution

> Tested Python solution for LeetCode 953 with 18 pytest cases. Generate a practice environment with lcpy.

LeetCode 953, Easy. Topics: Array, Hash Table, String. [View on LeetCode](https://leetcode.com/problems/verifying-an-alien-dictionary/description/).

Generate this problem as a practice environment: tested reference solution, 18 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 953   # by problem number
lcpy gen -s verifying_an_alien_dictionary   # by problem name
```

## Problem

In an alien language, surprisingly, they also use English lowercase letters, but possibly in a different `order`. The `order` of the alphabet is some permutation of lowercase letters.

Given a sequence of `words` written in the alien language, and the `order` of the alphabet, return `true` if and only if the given `words` are sorted lexicographically in this alien language.

### Examples

```
Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output: true
Explanation: As 'h' comes before 'l' in this language, then the sequence is sorted.
```

```
Input: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
Output: false
Explanation: As 'd' comes after 'l' in this language, then words[0] > words[1], hence the sequence is unsorted.
```

```
Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
Output: false
Explanation: The first three characters "app" match, and the second string is shorter (in size.) According to lexicographical rules "apple" > "app".
```

### Constraints

* 1 \<= words.length \<= 100
* 1 \<= words\[i].length \<= 20
* `order.length == 26`
* All characters in `words[i]` and `order` are English lowercase letters.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/verifying_an_alien_dictionary/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/verifying_an_alien_dictionary/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(m) where m is total characters across all words
    # Space: O(1)
    def is_alien_sorted(self, words: list[str], order: str) -> bool:
        rank = {ch: i for i, ch in enumerate(order)}

        def less_or_equal(word1: str, word2: str) -> bool:
            for ch1, ch2 in zip(word1, word2, strict=False):
                if rank[ch1] < rank[ch2]:
                    return True
                if rank[ch1] > rank[ch2]:
                    return False
            return len(word1) <= len(word2)

        return all(less_or_equal(words[i], words[i + 1]) for i in range(len(words) - 1))
```

## Complexity

| Time                                              | Space |
| ------------------------------------------------- | ----- |
| O(m) where m is total characters across all words | O(1)  |

## Tags

[NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode).