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 indexOf actually 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?