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 <= 1001 <= words[i].length <= 20order.length == 26- All characters in
words[i]andorderare 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();
}
}
Input
words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output
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;
}
};
Input
words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output
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
Input
words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
Output
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;
}
}
}
Input
words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
Output
false