# 953. 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 lexicographicaly in this alien language.

### Constraints

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

### Approach

### Links

* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/verifying-an-alien-dictionary/)
* ProgramCreek
* YouTube

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:** words = \["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"

**Output:** true

**Explanation:** As 'h' comes before 'l' in this language, then the sequence is sorted.
{% endtab %}

{% tab title="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.
{% endtab %}

{% tab title="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).
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(M), M be the total number of characters in words.
 * Space complexity : O(1)
 */

class Solution {
    private final int[] alienAlphaTable = new int[26];
    
    public boolean isAlienSorted(String[] words, String order) {
        if(words == null || words.length <= 1) {
            return true;
        }
        for(int i = 0; i < 26; i++) {
            alienAlphaTable[order.charAt(i)-'a'] = i;
        }
        for(int i = 0; i < words.length-1; i++) {
            if(isBigger(words[i], words[i+1])) {
                return false;
            }
        }
        return true;
    }
    
    private boolean isBigger(String word1, String word2) {
        int minLen = Math.min(word1.length(), word2.length());
        for(int i = 0; i < minLen; i++) {
            char ch1 = word1.charAt(i);
            char ch2 = word2.charAt(i);
            if(ch1 != ch2) {
                return alienAlphaTable[ch1-'a'] > alienAlphaTable[ch2-'a'];
            }
        }
        return word1.length() > word2.length();
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*