# LeetCode 953. Verifying an Alien Dictionary

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

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

[English Version in Youtube](https://youtu.be/jwL1Q70YNso)

[中文版解答Youtube Link](https://youtu.be/Ou-28FTq00g)

[中文版解答Bilibili Link](https://www.bilibili.com/video/BV1gK4y1U7Bp/)

```
class Solution {
    
    bool check(const string& previous_word, const string& current_word, char* orders) {
        int len = min(previous_word.length(), current_word.length());
        for (int i = 0; i < len; i++) {
            char p_ch = previous_word[i];
            char c_ch = current_word[i];
            if (orders[p_ch - 'a'] < orders[c_ch - 'a']) return true;
            if (orders[p_ch - 'a'] > orders[c_ch - 'a']) return false;
        }
        return previous_word <= current_word;
    }
    
public:
    bool isAlienSorted(vector<string>& words, string order) {
        char orders[26];
        for (int i = 0; i < order.length(); i++) {
            orders[order[i] - 'a'] = i;
        }
        
        for (int i = 1; i < words.size(); i++) {
            const string& previous_word = words[i - 1];
            const string& current_word = words[i];
            if (!check(previous_word, current_word, orders)) {
                return false;
            }
        }
        
        return true;
    }
};
```
