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 lexicographicaly 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 <= 100
1 <= words[i].length <= 20
order.length == 26
All characters in words[i] and order are English lowercase letters.

Difficulty: introductory

Starter code:

class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        

Solutions:
class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        char_map = {char: i for i, char in enumerate(order)}
        for j in range(1, len(words)):
            prev, curr = words[j - 1], words[j]

            k = 0
            while k < min(len(prev), len(curr)):
                if prev[k] == curr[k]:
                    k += 1
                elif char_map[prev[k]] > char_map[curr[k]]:
                    return False
                else:
                    break
            if k >= len(curr):
                return False
        return True

class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        record = {o:i for i, o in enumerate(order)}
        
        def checkOrdered(w1, w2):
            p = min(len(w1), len(w2))
            i = 0
            while(i < p):
                if w1[i] == w2[i]:
                    i += 1
                else:
                    break
            if i != p:
                l, r = record[w1[i]], record[w2[i]]
                # l, r = order.index(w1[i]),order.index(w2[i]) 
                if l < r:
                    return True
                if l > r:
                    return False
            else:
                return len(w1) <= len(w2)
            
        if len(words) <= 1:
            return True
        
        left = self.isAlienSorted(words[:len(words)//2], order)
        mid = checkOrdered(words[len(words)//2-1], words[len(words)//2])
        right = self.isAlienSorted(words[len(words)//2:], order)
        

        return left and right and mid


class Solution:
    def alienCompare(self, word1: str, word2: str, order: str) -> int:
        if word1 == word2:
            return 0
        else:
            i: int = 0
            while i < len(word1) and i < len(word2) and word1[i] == word2[i]:
                i += 1
            if i == len(word1):
                return -1
            elif i == len(word2):
                return 1
            elif order.index(word1[i]) < order.index(word2[i]):
                return -1
            else:
                return 1
    
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        n: int = len(words)
        if n == 0 or n == 1:
            return True
        else:
            for i in range(1, n):
                if self.alienCompare(words[i - 1], words[i], order) == 1:
                    return False
            return True

class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        # shorter strings with common alphabets are always preferred in ordering
        # given the order, a O(m) dictionary mapping letter to a number can be made
        # and by iterating through every word and computing the sum of numbers,
        # when the number is smaller for earlier one, then terminate with False
        # if the loop finishes without returning False, then return True
        
        if len(words) == 1:
            return True
        
        i = 0

        lex_dict = {l: o for o, l in enumerate(order)}
        print(lex_dict)
        # for o in range(len(order)):
        #     lex_dict[order[o]] = o + 1

        # instead of scrolling through each letter in all words,
        # just compare the pairs in the order (list is an ordered data structure anyway)
        
        prev_word = words[0]
        for i in range(1, len(words)):
            word = words[i]
            # do comparison
            # print(\"prev_word: {}, word: {}\".format(prev_word, word))
            for l1, l2 in zip(prev_word, word):
                if lex_dict[l2] < lex_dict[l1]:
                    return False
                elif lex_dict[l2] > lex_dict[l1]:
                    break  # no need for further checking
            # # handle special case, if it survived and the length of prev_word is > word, return False
            else:  # amazing trick! if no breakpoint occurred in the above for-loop, then come here
                if len(prev_word) > len(word):
                    return False
            prev_word = word            
            
                    
        return True


class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        for i in range(len(words)-1):
            s1,s2 = words[i],words[i+1]
            if not self.checkWords(s1,s2,order):
                return False
        return True
    
    def checkWords(self,s1,s2,order):
        for i in range(len(s1)):
            if i < len(s2):
                if s1[i] != s2[i]:
                    if order.index(s1[i]) > order.index(s2[i]): return False
                    return True
            else:
                return False
        return True

class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        index_lookup = {char: i for i,char in enumerate(order)}
        for i in range(len(words) - 1):
            first, second = words[i:i+2]
            for j in range(min(len(first), len(second))):
                if first[j] != second[j]:
                    if index_lookup[first[j]] > index_lookup[second[j]]:
                        return False
                    break
            else:
                if len(first) > len(second):
                    return False
        return True


class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        '''
        Questions:are all char in the order? any missing? any duplicates?
        
        O(wn) len of longest word, compare all words
        order would be in a map to see
        
        '''
        word_indexes = {ch : i for i, ch in enumerate(list(order))}
        
        for i, word1 in enumerate(words[1:], start=1):
            word2 = words[i-1] # word before
            
            for j in range(min(len(word1), len(word2))):
                if word1[j] != word2[j]: # only compare when they are different
                    if word_indexes[word1[j]] < word_indexes[word2[j]]:
                        return False
                    break
            else: # when break not hit
                # complete word but there is more characters for one of the words: 
                # should be ordered after the shorter word
                if len(word1) < len(word2):
                    # word before is longer
                    return False
        
        return True

class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        d = {c: i for i, c in enumerate(order)}
        def compare(w1, w2):
            for i in range(min(len(w1), len(w2))):
                if d[w1[i]] < d[w2[i]]:
                    return True
                if d[w1[i]] > d[w2[i]]:
                    return False
            return len(w1) <= len(w2)
        
        for i in range(len(words) - 1):
            if not compare(words[i], words[i+1]):
                return False
        
        return True

class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        order_index = {c: i for i, c in enumerate(order)}

        for i in range(len(words) - 1):
            word1 = words[i]
            word2 = words[i+1]

            # Find the first difference word1[k] != word2[k].
            for k in range(min(len(word1), len(word2))):
                # If they compare badly, it's not sorted.
                if word1[k] != word2[k]:
                    if order_index[word1[k]] > order_index[word2[k]]:
                        return False
                    break
            else:
                # If we didn't find a first difference, the
                # words are like (\"app\", \"apple\").
                if len(word1) > len(word2):
                    return False

        return True

class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        
        order_map = {c: i for i, c in enumerate(order)}
        
        words = [[order_map[w] for w in word] for word in words]
        
        return all([w1<=w2 for w1,w2 in zip(words, words[1:])])