> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0953-verifying-an-alien-dictionary.md).

# 0953. Verifying an Alien Dictionary

<https://leetcode.com/problems/verifying-an-alien-dictionary>

## Description

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_order)).
```

**Constraints:**

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

## ac

```java
class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        // Edge cases
        if (words.length <= 1) {
            return true;
        }
        
        int[] letterOrder = new int[26];
        for (int i = 0; i < order.length(); i++) {
            char c = order.charAt(i);
            letterOrder[c-'a'] = i;
        }
        
        for (int i = 1; i < words.length; i++) {
            if (!isCorrectOrder(words[i-1], words[i], letterOrder)) return false;
        }
        
        return true;
    }
    
    private boolean isCorrectOrder(String word1, String word2, int[] letterOrder) {
        int len1 = word1.length();
        int len2 = word2.length();
        for (int i = 0; i < len1 && i < len2; i++) {
            if (word1.charAt(i) == word2.charAt(i)) continue;
            // Meet different char
            int order1 = letterOrder[word1.charAt(i) - 'a'];
            int order2 = letterOrder[word2.charAt(i) - 'a'];
            return order1 < order2;
        }
        
        // 1) 2 words are the same; 2) word1 is prefix of word2, e.g. [app, apple]
        return len1 <= len2;
    }
}
// Key: how to compare order in a array - just compare every 2 items
// O(NS) time: N - length of words array, S - average length of word. O(1) space.
```