# 0953. Verifying an Alien Dictionary

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Verifying an Alien Dictionary](https://leetcode.com/problems/verifying-an-alien-dictionary/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0953-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 lexicographically in this alien language.**
{% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**Constraints:**

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

```
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", because 'l' > '∅', where '∅' is defined as the blank character which is less than any other character.
```

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
**Lexicographical order** in English\
1\. Correct order for \[apple, book]\
2\. Correct order for \[backtrack, backwords]\
3\. Wrong order for \[apple, app]. Should be \[app, apple]
{% endhint %}

First, we **build the order using the hash table or array** according to the input order. Then, we **iterate through each word in the words to check it with the adjacent word**.

> **Check Conditions**
>
> 1. **Current index + 1 (current length) is larger than next word's length, return False**\
>    For the first iteration (index = 0), this check does not work since each word has 1 as MIN length. After passing the first iteration with second check, this check will be effective.
> 2. Current word and the adjacent word **have different char in the same index**
>    * **Check their order**, if violate, return False.&#x20;
>    * **Otherwise, break to the next iteration** (since they are in the correct order).
>      {% endtab %}
>      {% endtabs %}

{% tabs %}
{% tab title="🤖 Python3" %}

```python
class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        
        # ==================================================
        #  String                                          =
        # ==================================================
        # time  : O(M), M is the total number of chars in words
        # space : O(1)
        
        table = dict()
        for i in range(len(order)): table[order[i]] =  i
            
        for i in range(len(words) - 1):
            for j in range(len(words[i])):
                # (current string's length > adjacent string's length)
                if j+1 > len(words[i+1]): return False
                
                if words[i][j] != words[i+1][j]:
                    if table[words[i][j]] > table[words[i+1][j]]: return False
                    break
                    
        return True
```

{% endtab %}

{% tab title="🤖 Java" %}

```java
class Solution {
    /**
     * @time  : O(M), M is the total number of chars in words
     * @space : O(1)
     */
    
    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++) {
            for (int j=0; j<words[i].length(); j++) {
                /* 
                    If we do not find a mismatch letter between words[i] and words[i + 1],
                    we need to examine the case when words are like ("apple", "app").
                */
                if (j+1 > words[i+1].length()) return false;

                if (words[i].charAt(j) != words[i+1].charAt(j)) {
                    int currentWordChar = words[i].charAt(j) - 'a';
                    int nextWordChar = words[i+1].charAt(j) - 'a';
                    
                    if (orderMap[currentWordChar] > orderMap[nextWordChar]) return false;
                    
                    /* 
                        If we find the first different letter and they are sorted,
                        then there's no need to check remaining letters
                    */
                    else break;
                }
            }
        }

        return true;
    }
}
```

{% endtab %}
{% endtabs %}