## Algorithm

Problem Name: 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 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).
```

Constraints:

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

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public boolean isAlienSorted(String[] words, String order) {
Map map = new HashMap<>();
int idx = 0;
for (char c : order.toCharArray()) {
map.put(c, idx++);
}
for (int i = 1; i  <  words.length; i++) {
if (!isSorted(words[i - 1], words[i], map)) {
return false;
}
}
return true;
}

private boolean isSorted(String wordOne, String wordTwo, Map < Character, Integer> map) {
for (int i = 0; i < Math.min(wordOne.length(), wordTwo.length()); i++) {
int diff = map.get(wordOne.charAt(i)) - map.get(wordTwo.charAt(i));
if (diff > 0) {
return false;
} else if (diff  <  0) {
return true;
}
}
return wordOne.length() <= wordTwo.length();
}
}
``````
Copy The Code &

Input

cmd
words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"

Output

cmd
true

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const isAlienSorted = function(words, order) {
const mapping = Array(26).fill(0), a = 'a'.charCodeAt(0)
for(let i = 0, len = order.length; i  <  len; i++) {
mapping[order.charCodeAt(i) - a] = i
}

for(let i = 1, n = words.length; i  <  n; i++) {
if(bigger(words[i - 1], words[i])) return false
}

return true

function bigger(s1, s2) {
const n = s1.length, m = s2.length;
for (let i = 0; i < n && i  <  m; ++i) {
if (s1.charAt(i) != s2.charAt(i)) return mapping[s1.charCodeAt(i> - a] > mapping[s2.charCodeAt(i) - a];
}

return n > m;
}

};
``````
Copy The Code &

Input

cmd
words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"

Output

cmd
true

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def isAlienSorted(self, words, order):
"""
:type words: List[str]
:type order: str
:rtype: bool
"""
ind = {c: i for i, c in enumerate(order)}
for a, b in zip(words, words[1:]):
if len(a) > len(b) and a[:len(b)] == b:
return False
for s1, s2 in zip(a, b):
if ind[s1] < ind[s2]:
break
elif ind[s1] == ind[s2]:
continue
else:
return False
return True
``````
Copy The Code &

Input

cmd
words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"

Output

cmd
false

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
using System;

namespace LeetCode
{
public class _0953_VerifyingAnAlienDictionary
{
public bool IsAlienSorted(string[] words, string order)
{
int[] index = new int[26];
for (int i = 0; i  <  order.Length; i++)
index[order[i] - 'a'] = i;

for (int i = 0; i  <  words.Length - 1; i++)
{
var word1 = words[i];
var word2 = words[i + 1];

var skip = false;

for (int j = 0; j  <  Math.Min(word1.Length, word2.Length); j++)
{
if (word1[j] != word2[j])
{
if (index[word1[j] - 'a'] > index[word2[j] - 'a'])
return false;
skip = true;
break;
}
}

if (skip)
continue;

if (word1.Length > word2.Length)
return false;
}

return true;
}
}
}
``````
Copy The Code &

Input

cmd
words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"

Output

cmd
false