跳转至

剑指 Offer II 034. 外星语言是否排序

题目描述

某种外星语也使用英文小写字母，但可能顺序 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 中的所有字符都是英文小写字母。

 

注意：本题与主站 953 题相同： https://leetcode.cn/problems/verifying-an-alien-dictionary/

解法

方法一

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        index = {c: i for i, c in enumerate(order)}
        for i in range(len(words) - 1):
            w1, w2 = words[i], words[i + 1]
            l1, l2 = len(w1), len(w2)
            flag = False
            for j in range(max(l1, l2)):
                i1, i2 = (
                    -1 if j >= l1 else index[w1[j]],
                    -1 if j >= l2 else index[w2[j]],
                )
                if i1 > i2:
                    # 说明不是按字典序排序，直接返回False
                    return False
                if i1 < i2:
                    # 说明当前两单词是按字典序排序，无需再往下进行循环比较
                    break
        return True

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        int[] index = new int[26];
        for (int i = 0; i < index.length; ++i) {
            index[order.charAt(i) - 'a'] = i;
        }
        for (int i = 0; i < words.length - 1; ++i) {
            String w1 = words[i];
            String w2 = words[i + 1];
            int l1 = w1.length(), l2 = w2.length();
            for (int j = 0; j < Math.max(l1, l2); ++j) {
                int i1 = j >= l1 ? -1 : index[w1.charAt(j) - 'a'];
                int i2 = j >= l2 ? -1 : index[w2.charAt(j) - 'a'];
                if (i1 > i2) {
                    // 说明不是按字典序排序，直接返回False
                    return false;
                }
                if (i1 < i2) {
                    // 说明当前两单词是按字典序排序，无需再往下进行循环比较
                    break;
                }
            }
        }
        return true;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool isAlienSorted(vector<string>& words, string order) {
        vector<int> index(26);
        for (int i = 0; i < index.size(); ++i)
            index[order[i] - 'a'] = i;
        for (int i = 0; i < words.size() - 1; ++i) {
            string w1 = words[i];
            string w2 = words[i + 1];
            int l1 = w1.size(), l2 = w2.size();
            for (int j = 0; j < max(l1, l2); ++j) {
                int i1 = j >= l1 ? -1 : index[w1[j] - 'a'];
                int i2 = j >= l2 ? -1 : index[w2[j] - 'a'];
                if (i1 > i2)
                    return false;
                if (i1 < i2)
                    break;
            }
        }
        return true;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func isAlienSorted(words []string, order string) bool {
    index := make(map[byte]int)
    for i := range order {
        index[order[i]] = i
    }
    for i := 0; i < len(words)-1; i++ {
        w1, w2 := words[i], words[i+1]
        l1, l2 := len(w1), len(w2)
        flag := true
        for j := 0; j < min(l1, l2) && flag; j++ {
            i1, i2 := index[w1[j]], index[w2[j]]
            if i1 > i2 {
                return false
            }
            if i1 < i2 {
                flag = false
            }
        }
        if flag && l1 > l2 {
            return false
        }
    }
    return true
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
function isAlienSorted(words: string[], order: string): boolean {
    let charMap = new Map();
    for (let i = 0; i < order.length; i++) {
        charMap.set(order[i], i);
    }
    function compare(str1: string, str2: string): boolean {
        const n = Math.min(str1.length, str2.length);
        for (let i = 0; i < n; i++) {
            let k1 = str1[i],
                k2 = str2[i];
            if (k1 != k2) return charMap.get(k1) < charMap.get(k2);
        }
        return n == str1.length;
    }
    for (let i = 1; i < words.length; i++) {
        if (!compare(words[i - 1], words[i])) return false;
    }
    return true;
}

评论