Jianbo Dai's

mq038.验证外星语词典

 
  • Dec 08, 2020

题目链接

emmm直接把列表里的单词每个都按顺序翻译了一遍再检查是否是已经按照英语的排序正确了。这个算法的时间复杂度是O（NlogN），空间复杂度是O（N）。但是由于我们这样将每个字符都翻译了一遍其实没有必要，更快的实现如2所示，依次比较相邻的两个单词即可，比较都过程是依次比较第一个不同的字母的index是否满足顺序关系，这种方法的一个特殊情况就是当单词不等长的时候要先判断一下。这个算法的时间复杂度是O（N），空间复杂度是O（1）。

class Solution:
    def isAlienSorted1(self, words: List[str], order: str) -> bool:
        eng = [chr(ord("a")+x) for x in range(26)]
        other = [x for x in order]
        pre = [(a, b) for a, b in zip(other, eng)]
        d = dict(pre)
        translated = []
        for w in words:
            tr_word = "".join([d[x] for x in w])
            translated.append(tr_word)
        return sorted(translated) == translated

    def isAlienSorted2(self, words, order):
        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
Search