HackMD
Leetcode #953. Verifying an Alien Dictionary
tags:String Easy
Problem
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.
Sample Input and Output
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 2
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
Solutions
Official
class Solution:
def isAlienSorted(self, words: List[str], order: str) -> bool:
order_map = {}
for index, val in enumerate(order):
order_map[val] = index
for i in range(len(words) - 1):
for j in range(len(words[i])):
# 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 >= len(words[i + 1]): return False
if words[i][j] != words[i + 1][j]:
if order_map[words[i][j]] > order_map[words[i + 1][j]]: return False
# if we find the first different character and they are sorted,
# then there's no need to check remaining letters
break
return True
Complexity analysis
Let N be the length of order, and M be the total number of characters in words.
Time complexity : O(M)
Storing the letter-order relation of each letter takes O(N) time. For the nested for-loops, we examine each pair of words in the outer-loop and for the inner loop, we check each letter in the current word. Therefore, we will iterate over all of letters in words.
Taking both into consideration, the time complexity is O(M+N). However, we know that N is fixed as 26. Therefore, the time complexity is O(M).
Space complexity : O(1)
The only extra data structure we use is the hashmap/array that serves to store the letter-order relations for each word in order. Because the length of order is fixed as 26, this approach achieves constant space complexity.
Everyone's
月
/* Time: O(n + m) | Space O(1)
n is the length of words. m is the same number of characters.
*/
var isAlienSorted = function(words, order) {
for(let i = 0; i < words.length ; i+=1){
const word = words[i];
const next = words[i+1];
let pointer = 0;
while (word[pointer] === next[pointer]) pointer++;
if(order.indexOf(word[pointer]) > order.indexOf(next[pointer])
|| !next[pointer]) return false;
return true
}
};
- This solution does NOT pass all the test case
- for loop should be
i < words.length - 1? - use
indexOfactually increase time complexity? - Question: why time complexity is
O(m+n)?
Hao
/**
* Time complexity: O(s) which s stands for the sum of each word.length
* Space complexity: O(1)
*/
var isAlienSorted = function(words, order) {
const charOrderDict = order.split('').reduce((acc, char, idx) => ({ ...acc, [char]: idx }), {});
const isTwoStrSorted = (former, latter) => {
let res;
let j = 0;
while (res === undefined) {
const charFr = former[j];
const charLr = latter[j];
if (charFr === undefined || charLr === undefined) {
if (charFr !== undefined && charLr === undefined) res = false;
else res = true;
}
if (charOrderDict[charFr] < charOrderDict[charLr]) res = true;
else if (charOrderDict[charFr] > charOrderDict[charLr]) res = false;
j += 1;
}
return res;
};
for (let i = 0; i < words.length - 1; i += 1) {
if (!isTwoStrSorted(words[i], words[i + 1])) return false;
}
return true;
};
Question: why time complexity is O(s), which s stands for the sum of each word.length?
東
Solution 1: use hash map to store the order
/* Time O(m * n) | Space O(1)
m is number of input word
n is the longest charaters of all input words
Note: It actually cost some memory to store order into a hash map, but it's constant space since there is fixed number of order input character
*/
var isAlienSorted = function(words, order) {
const orderHash = {};
for(let i = 0; i < order.length; i++){
orderHash[order[i]] = i;
}
for(let i = 0; i < words.length - 1; i++){
const [currWord, nextWord] = [words[i], words[i+1]];
for(let charIdx = 0; charIdx < currWord.length; charIdx++){
const [currWordChar, nextWordChar] = [currWord[charIdx], nextWord[charIdx]];
if(charIdx === nextWord.length) return false;
if(currWordChar !== nextWordChar){
if(orderHash[currWordChar] > orderHash[nextWordChar]) return false;
else break;
}
}
}
return true;
};
Solution 2: use string.indexOf
/* Time O(m * n) | Space O(1)
m is number of input word
n is the longest charaters of all input words
Note: use indexOf to find actually cost some more time, but it's constant time since there is fixed number of order input character
*/
var isAlienSorted = function(words, order) {
for(let i = 0; i < words.length - 1; i++){
const [currWord, nextWord] = [words[i], words[i+1]];
for(let charIdx = 0; charIdx < currWord.length; charIdx++){
const [currWordChar, nextWordChar] = [currWord[charIdx], nextWord[charIdx]];
if(charIdx === nextWord.length) return false;
if(currWordChar !== nextWordChar){
if(order.indexOf(currWordChar) > order.indexOf(nextWordChar)) return false;
else break;
}
}
}
return true;
};
YC
/*
time: O(n); - where n is the amount of the characters in the words array
space: O(1);
*/
var isAlienSorted = function(words, order) {
const orderMap = new Map();
for(let i = 0; i < order.length; i++){
orderMap.set(order[i], i);
}
for(let i = 0; i < words.length - 1; i++){
for(let j = 0; j < words[i].length; j++){
if(j >= words[i + 1].length) {
return false;
}
const charFront = words[i][j];
const charBack = words[i + 1][j];
if(orderMap.get(charFront) === orderMap.get(charBack)){
continue;
}
else if (orderMap.get(charFront) < orderMap.get(charBack)){
break;
}
else{
return false;
}
}
}
return true;
};
Supplement / Discussion
Time complexity
- Why nested for loop does not increase time complexity?
