leetcode 953. 验证外星语词典

题目描述
解题思路
执行结果

题目描述

验证外星语词典

某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。

给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，返回 true；否则，返回 false。

示例 1：

输入：words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz" 输出：true 解释：在该语言的字母表中，'h' 位于 'l' 之前，所以单词序列是按字典序排列的。示例 2：

输入：words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz" 输出：false 解释：在该语言的字母表中，'d' 位于 'l' 之后，那么 words[0] > words[1]，因此单词序列不是按字典序排列的。示例 3：

输入：words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz" 输出：false 解释：当前三个字符 "app" 匹配时，第二个字符串相对短一些，然后根据词典编纂规则 "apple" > "app"，因为 'l' > '∅'，其中 '∅' 是空白字符，定义为比任何其他字符都小（更多信息）。

提示：

1 <= words.length <= 100 1 <= words[i].length <= 20 order.length == 26 在 words[i] 和 order 中的所有字符都是英文小写字母。

解题思路

法1

哈希表+模拟

建立map[byte]int,其中key为字符,value为位置,
遍历字符串中的字母,检查是否,字符顺序是否按order给的顺序,后一个的value始终大于前一个,如果不是返回false,如果继续遍历下一个
结束返回真

时间复杂度(O(n))
空间复杂度(O(n))

执行结果

法1

首先，我们遍历order字符串，将每个字符与其在字符串中的位置建立映射关系，存储到字典表dict中。

然后，我们逐个比较相邻的单词，通过compareWords函数来检查它们的顺序是否正确。在compareWords函数中，我们首先获取两个单词的长度，并找到它们长度的较小值。然后，我们按照单词中字符的顺序逐个比较它们在字典表dict中的索引。如果在某个位置上，第一个单词的字符的索引小于第二个单词的字符的索引，说明它们的顺序是正确的，返回true。如果在某个位置上，第一个单词的字符的索引大于第二个单词的字符的索引，说明它们的顺序是错误的，返回false。如果两个单词在前面的所有位置上的字符索引都相同，那么长度较短的单词应该排在前面，因此返回len1 <= len2，其中len1和len2分别为两个单词的长度。

最后，我们遍历完所有的相邻单词后，如果没有发现顺序错误的情况，就返回true，表示给定的单词在外星语中按字典序排列；否则，返回false。

func isAlienSorted(words []string, order string) bool {
    dict := make(map[byte]int)

    // 构建字典表，记录字母顺序的索引
    for i := 0; i < len(order); i++ {
        dict[order[i]] = i
    }

    // 检查相邻单词的顺序是否正确
    for i := 1; i < len(words); i++ {
        if !compareWords(words[i-1], words[i], dict) {
            return false
        }
    }

    return true
}

// 比较两个单词的顺序
func compareWords(word1, word2 string, dict map[byte]int) bool {
    len1, len2 := len(word1), len(word2)
    minLen := min(len1, len2)

    for i := 0; i < minLen; i++ {
        if dict[word1[i]] < dict[word2[i]] {
            return true
        } else if dict[word1[i]] > dict[word2[i]] {
            return false
        }
    }

    return len1 <= len2
}

// 返回两个整数的最小值
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}