# 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 > words, hence the sequence is unsorted.```

Intuition

The words are sorted lexicographically if and only if adjacent words are. This is because order is transitive: `a <= b` and `b <= c` implies `a <= c`.

Algorithm

Let’s check whether all adjacent words `a` and `b` have `a <= b`.

To check whether `a <= b` for two adjacent words `a` and `b`, we can find their first difference. For example, `"applying"` and `"apples"` have a first difference of `y` vs `e`. After, we compare these characters to the index in `order`.

Care must be taken to deal with the blank character effectively. If for example, we are comparing `"app"` to `"apply"`, this is a first difference of `(null)` vs `"l"`.

```class Solution {
public boolean isAlienSorted(String[] words, String order) {
Map<Character, Integer> characterOrderMap = new HashMap<>();
for (int i = 0; i < order.length(); i++) {
characterOrderMap.put(order.charAt(i), i);
}
for (int i = 0; i < words.length - 1; i++) {
if (!compare(words[i], words[i + 1], map)){
return false;
}
}
return true;
}

private boolean compare(String s1, String s2, Map<Character, Integer> characterOrderMap) {
int l1 = s1.length(), l2 = s2.length();
for (int i = 0, j = 0; i < l1 && j < l2; i++, j++) {
if (s1.charAt(i) != s2.charAt(j)) {
if (map.get(s1.charAt(i)) > characterOrderMap.get(s2.charAt(j))) {
return false;
} else {
return true;
}
}
}
if (l1 > l2) return false;
return true;
}
}
```

Complexity Analysis

• Time Complexity: `O(C)`, where `C` is the total content of `words`.
• Space Complexity: `O(1)`.

Categories: Map

Tagged as: