LC 0953 [E] Verifying an Alien Dictionary - ALawliet/algorithms GitHub Wiki

intuitive? N

• build order hashmap of char => index for fast lookups
• loop zip pairs of word with adjacent word w1, w2 in zip(words, words[1:])
• loop zip pairs of chars in the words c1, c2 in zip(w1, w2)

check cases:

1. chars are same => continue
2. if not same, look up in order in hashmap => return False if chars not in order, break to next word for first one that is True
3. prefix edge case: if no break (chars in shorter word exhausted) => return False if w1 does not come first because shorter word with blank should be lexico first, but use <= to check for same word because this should not return False

gotchas:

• if two words are the same ['hello', 'hello']
• if one word is exhausted early ['apple', 'app], ['kuvp', 'q']

T: O(C) where C is the total content in words
S: O(1)

---

class Solution:
    def isAlienSorted(self, words, order):
        d = {}
        for i, c in enumerate(order):
            d[c] = i

        for w1, w2 in zip(words, words[1:]):
            for c1, c2 in zip(w1, w2):
                if c1 == c2: continue

                # don't have to check <= because == handled by continue
                if not d[c1] < d[c2]: 
                    return False
                else:
                    break # just have to check first pair of chars, then break to next word

            else: # we exhausted all the characters in the shorter word with == and no failures
                # now len of w1 must be shorter or at least the same
                if not len(w1) <= len(w2):
                    return False

        return True

class Solution:
    def isAlienSorted(self, words, order):
        # compare 2 words at a time
        # compare 2 chars of each word at a time
        # use a hashmap fast lookup order
        
        d = {} # order_to_index
        for i in range(len(order)):
            d[order[i]] = i

        print(d)
            
        for w1, w2 in zip(words, words[1:]):
            print(w1, w2)
            
            for c1, c2 in zip(w1, w2):
                print(c1, c2)
                # if the chars are the same, skip this pair of chars and go to the next
                if c1 == c2: continue # to next chars
                
                # if they are not, then we are out of order
                if not d[c1] < d[c2]: return False # can be < or <=
                
                # else we are good, skip the rest of chars and go to next word
                break # to next words
                # if we skipped the chars cuz they passed, then just continue to the next word

            # if we just finished looping (no breaks) thru all the chars of the shorter string, then check the lengths
            else:
                # we exhausted the shorter string from the loop, which should have been in the 1st position because blank < any other char
                if not len(w1) <= len(w2): return False

            # to next words
                
        return True