# Verifying an Alien Dictionary
**Difficulty:** EASY
[External](https://leetcode.com/problems/verifying-an-alien-dictionary)
Canonical: https://scaleengineer.com/dsa/problems/verifying-an-alien-dictionary
**Data structures:** Array, Hash Table, String
**Companies:** [Wix](https://scaleengineer.com/companies/wix), [Snap](https://scaleengineer.com/companies/snap)
---
## 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.

**Example 1:**

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

**Example 2:**

**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.

**Example 3:**

**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", because 'l' > '∅', where '∅' is defined as the blank character which is less than any other character ([More info](https://en.wikipedia.org/wiki/Lexicographical%5Forder)).

**Constraints:**

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

# Approaches
## Brute-Force Comparison with Linear Search
This approach involves iterating through each adjacent pair of words in the input list and comparing them character by character. For each pair of differing characters, we find their positions in the `order` string using a linear search (`indexOf`) to determine their relative rank. If we find any pair of words that is out of order, we immediately return `false`.
**Time:** O(N * M * L), where N is the number of words, M is the maximum length of a word, and L is the length of the `order` string (26). For each of the N-1 pairs of words, we might compare up to M characters. For each character comparison, we perform `indexOf`, which takes O(L) time. · **Space:** O(1), as we only use a few variables to store indices and characters, not dependent on the input size.
**Pros:** Simple to understand and implement.; Requires no extra space.
**Cons:** Inefficient due to the repeated linear search (`indexOf`) within the `order` string for every character comparison.
### Explanation
The core idea is to verify the sorted property by checking every two adjacent words. If `words[i]` should come after `words[i+1]` for any `i`, then the array is not sorted. The comparison between two words is done character by character, and the relative order of two different characters is determined by finding their index in the `order` string.

```java
class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        for (int i = 0; i < words.length - 1; i++) {
            String word1 = words[i];
            String word2 = words[i + 1];
            int minLength = Math.min(word1.length(), word2.length());
            boolean different = false;
            for (int j = 0; j < minLength; j++) {
                char c1 = word1.charAt(j);
                char c2 = word2.charAt(j);
                if (c1 != c2) {
                    if (order.indexOf(c1) > order.indexOf(c2)) {
                        return false;
                    }
                    different = true;
                    break;
                }
            }
            if (!different && word1.length() > word2.length()) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
*   Iterate through the `words` array from `i = 0` to `words.length - 2`.
*   For each `i`, take `word1 = words[i]` and `word2 = words[i+1]`.
*   Compare `word1` and `word2` character by character up to the length of the shorter word.
*   At the first differing character, find their positions in the `order` string using `indexOf()`.
*   If the character from `word1` has a higher index than the character from `word2`, the list is unsorted, so return `false`.
*   If the character from `word1` has a lower index, this pair is sorted. Break the character comparison and check the next pair of words.
*   If the words are identical up to the length of the shorter word (one is a prefix of the other), check their lengths. If `word1` is longer than `word2` (e.g., "apple", "app"), the list is unsorted, so return `false`.
*   If the entire loop completes, all pairs are sorted correctly. Return `true`.

## Comparison with Pre-computed Order Map
This approach improves upon the brute-force method by pre-processing the `order` string. We create a mapping from each character to its rank (position) in the alien alphabet. This allows for constant-time lookups of a character's rank, making the overall comparison process much faster.
**Time:** O(N * M + L), where N is the number of words, M is the maximum length of a word, and L is the length of the `order` string. The pre-computation takes O(L) time. The main comparison loop takes O(N * M) because we iterate through N-1 pairs and each comparison takes at most O(M) time with O(1) character rank lookups. Since L is a constant (26), the complexity is effectively O(N * M). · **Space:** O(L) or O(1), as we use an auxiliary array of size 26 to store the character rankings. Since the alphabet size is fixed, this is considered constant space.
**Pros:** Highly efficient due to O(1) character rank lookups.; The dominant part of the complexity comes from iterating through the words, which is necessary.
**Cons:** Requires a small amount of extra space for the mapping.
### Explanation
To optimize the character comparison, we can first build a data structure that maps each character to its position in the `order` string. An array of size 26 is perfect for this, as we are dealing with lowercase English letters. This pre-computation step takes a small, fixed amount of time but allows subsequent character rank lookups to be done in O(1) time, significantly speeding up the main comparison logic.

```java
class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        int[] orderMap = new int[26];
        for (int i = 0; i < order.length(); i++) {
            orderMap[order.charAt(i) - 'a'] = i;
        }

        for (int i = 0; i < words.length - 1; i++) {
            String word1 = words[i];
            String word2 = words[i + 1];
            int minLength = Math.min(word1.length(), word2.length());
            boolean different = false;
            for (int j = 0; j < minLength; j++) {
                char c1 = word1.charAt(j);
                char c2 = word2.charAt(j);
                if (c1 != c2) {
                    if (orderMap[c1 - 'a'] > orderMap[c2 - 'a']) {
                        return false;
                    }
                    different = true;
                    break;
                }
            }
            if (!different && word1.length() > word2.length()) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
*   **Preprocessing:** Create an integer array `orderMap` of size 26. Iterate through the `order` string and populate `orderMap` such that `orderMap[character - 'a']` stores the rank of the character.
*   **Comparison:** Iterate through adjacent pairs of words (`word1`, `word2`) in the `words` array.
*   Compare `word1` and `word2` character by character.
*   For each pair of characters `c1` and `c2`, get their ranks from `orderMap` in O(1) time.
*   If `rank(c1) > rank(c2)`, the list is unsorted. Return `false`.
*   If `rank(c1) < rank(c2)`, the pair is sorted. Move to the next pair of words.
*   Handle the prefix case: if `word1` is longer than `word2` and `word2` is a prefix of `word1`, return `false`.
*   If the loop finishes, return `true`.

# Solutions
### Java

```java
class Solution { public boolean isAlienSorted ( String [] words , String order ) { int [] m = new int [ 26 ]; for ( int i = 0 ; i < 26 ; ++ i ) { m [ order . charAt ( i ) - 'a' ] = i ; } for ( int i = 0 ; i < 20 ; ++ i ) { int prev = - 1 ; boolean valid = true ; for ( String x : words ) { int curr = i >= x . length () ? - 1 : m [ x . charAt ( i ) - 'a' ]; if ( prev > curr ) { return false ; } if ( prev == curr ) { valid = false ; } prev = curr ; } if ( valid ) { break ; } } return true ; } }
```

### CPP

```cpp
class Solution { public: bool isAlienSorted ( vector < string >& words , string order ) { vector < int > m ( 26 ); for ( int i = 0 ; i < 26 ; ++ i ) m [ order [ i ] - 'a' ] = i ; for ( int i = 0 ; i < 20 ; ++ i ) { int prev = - 1 ; bool valid = true ; for ( auto & x : words ) { int curr = i >= x . size () ? - 1 : m [ x [ i ] - 'a' ]; if ( prev > curr ) return false ; if ( prev == curr ) valid = false ; prev = curr ; } if ( valid ) break ; } return true ; } };
```

### Python

```python
class Solution : def isAlienSorted ( self , words : List [ str ], order : str ) -> bool : m = { c : i for i , c in enumerate ( order )} for i in range ( 20 ): prev = - 1 valid = True for x in words : curr = - 1 if i >= len ( x ) else m [ x [ i ]] if prev > curr : return False if prev == curr : valid = False prev = curr if valid : return True return True
```