# [Leetcode #953. Verifying an Alien Dictionary](https://leetcode.com/problems/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 

<br>

<hr/>

## 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

:::spoiler 月

/* 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)`?

:::

<br>

:::spoiler 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?

:::

<br>

:::spoiler 東

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;
};

:::

<br>

:::spoiler 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;
};

:::

<br>

---

## Supplement / Discussion

### Time complexity

- Why nested for loop does not increase time complexity?