953. Verifying an Alien Dictionary

[tech-cow]

953. Verifying an Alien Dictionary

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.

[tech-cow]

Final Version

class Solution(object):
    def isAlienSorted(self, words, alphabet):
        dic = {}
        for i, num in enumerate(alphabet):
            dic[num] = i
        
        n = len(words)
        for i in range(n):
            if i + 1 == n: return True
            word1 , word2 = words[i], words[i + 1]
            if self.leftIsLarger(word1, word2, dic):
                return False
        return True
    
    def leftIsLarger(self, word1, word2, dic):
        m, n = len(word1), len(word2)
        for i in range(min(m , n)):
            if word1[i] != word2[i]:
                if dic[word1[i]] > dic[word2[i]]:
                    return True
                else:
                    return False
        return m > n

[tech-cow]

Historical Struggle

'''
# Start [2:48]

# Problem Solving
    Brute Force
        Make a dict of dic(char:index)
        For loop through the words
            Compare 2 word at a time
                if all match and remain words on left, return False
'''

错误1 - 理解错题目意思

理解错误题目意思，应该是只要有一次word1的大小比word2小，就skip

# Coding [2:54] 
# 理解题目错误1

class Solution(object):
    def isAlienSorted(self, words, order):
        if not words or len(words) < 2: return True
        
        dic = {}
        for i, char in enumerate(order):
            dic[char] = i
        
        for i in range(len(words)):
            if i + 1 == len(words): 
                return True
        
            ind1, ind2 = 0, 0
            word1 , word2 = words[i], words[i + 1]
            
            while ind1 < len(word1) or ind2 < len(word2):
                if dic[word1[ind1]] > dic[word2[ind2]]:
                    print(word1[ind1], word2[ind2], 2)
                    return False
                ind1 += 1
                ind2 += 1
            
            if len(word2) > len(word1):
                print(1)
                return False
        
        return True
    

Pass代码, 总时长26分钟

# [3:06] 第二次尝试 
# [3:14] Pass

class Solution(object):
    def isAlienSorted(self, words, order):
        if not words or len(words) < 2: return True
        
        dic = {}
        for i, char in enumerate(order):
            dic[char] = i
        
        for i in range(len(words)):
            if i + 1 == len(words): 
                return True
        
            ind1, ind2 = 0, 0
            word1 , word2 = words[i], words[i + 1]
            flag = False
            
            while ind1 < len(word1) and ind2 < len(word2):
                if dic[word1[ind1]] < dic[word2[ind2]]:
                    flag = True
                    ind1 += 1
                    ind2 += 1
                    break
                elif dic[word1[ind1]] == dic[word2[ind2]]:
                    ind1 += 1
                    ind2 += 1
                    continue
                else:
                    return False
                
                ind1 += 1
                ind2 += 1
            
            if len(word2) < len(word1) and not flag:
                return False
        
            flag = False
        
        return True

代码快速简化

# 个人之后简化
class Solution(object):
    def isAlienSorted(self, words, order):
        if not words or len(words) < 2: return True
        dic = {}
        for i, char in enumerate(order):
            dic[char] = i
        
        for i in range(len(words)):
            if i + 1 == len(words): 
                return True
        
            ind1, ind2 = 0, 0
            word1 , word2 = words[i], words[i + 1]
            flag = False
            
            while ind1 < len(word1) and ind2 < len(word2):
                if dic[word1[ind1]] < dic[word2[ind2]]:
                    flag = True
                    break
                if dic[word1[ind1]] > dic[word2[ind2]]:
                    return False
                ind1 += 1 ; ind2 += 1
            
            if len(word2) < len(word1) and not flag:
                return False
            flag = False
        return True

代码重构

class Solution(object):
    def isAlienSorted(self, words, order):
        if not words or len(words) < 2: return True
        dic = {}
        for i, char in enumerate(order):
            dic[char] = i
        
        for i in range(len(words)):
            if i + 1 == len(words):  return True
            word1, word2 = words[i], words[i + 1]
            if self.isLeftBigger(word1, word2, dic):
                return False
        return True
        
    def isLeftBigger(self, word1, word2, dic):
        m, n = len(word1), len(word2)
        i , j = 0, 0 
        while i < m and j < n:
            if word1[i] != word2[j]:
                return dic[word1[i]] > dic[word2[j]]
            i += 1 ; j += 1
        return m > n

class Solution(object):
    def isAlienSorted(self, words, order):
        if not words or len(words) < 2: return True
        dic = {}
        for i, char in enumerate(order):
            dic[char] = i
        
        for i in range(len(words)):
            if i + 1 == len(words):  return True
            word1, word2 = words[i], words[i + 1]
            if self.isLeftBigger(word1, word2, dic):
                return False
        return True
        
    def isLeftBigger(self, word1, word2, dic):
        m, n = len(word1), len(word2)
        size = min(m, n)
        for i in range(size):
            if word1[i] != word2[i]:
                return dic[word1[i]] > dic[word2[i]]
        return m > n