0953. Verifying an Alien Dictionary
Easy | String + Hash Table | 28 ms (96.12%), 14.2 MB (91.25%)
Source: LeetCode - Verifying an Alien Dictionary GitHub: Solution / Performance
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.
Constraints:
1 <= words.length <= 1001 <= words[i].length <= 20order.length == 26All characters in
words[i]andorderare 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.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
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.
Current word and the adjacent word have different char in the same index
Check their order, if violate, return False.
Otherwise, break to the next iteration (since they are in the correct order).
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 Trueclass 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;
}
}Last updated
Was this helpful?