Verifying An Alien Dictionary

Intuition

• I think brute force is the accepted answer in this case. In fact, this isn’t exactly brute force. That is because optimizing by using the rule of transitivity, i.e. that word1 < word2, and word2 < word3, then word1 < word3, is already being done in my code.
• What I was thinking was that I could check horizontally len(words) characters at a time, but this adds a lot of complication and doesn’t actually help since you would be computing every string anyway in the worst case.
• In other words, for this specific problem marked as easy, there is no point in overcomplicating it.

Runtime

$O(NM)$, where N is the length of the array, and M is the length of the longest length string.

Code

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

Notes

---

References

https://leetcode.com/problems/verifying-an-alien-dictionary/