LeetCode Daily Question 11

Mar 16th 2022

3 月 16 日 每日一题

题目：953. Verifying an Alien Dictionary

In an alien language, surprisingly, they also use English lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters.

Given a sequence of words written in the alien language, and the order of the alphabet, return true if and only if the given words are sorted lexicographically in this alien language.

1
2
3
4
5
6
7
8
9
10
11
12
13
Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output: true
Explanation: As 'h' comes before 'l' in this language, then the sequence is sorted.
Example 2:

Input: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
Output: false
Explanation: As 'd' comes after 'l' in this language, then words[0] > words[1], hence the sequence is unsorted.
Example 3:

Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
Output: false
Explanation: The first three characters "app" match, and the second string is shorter (in size.) According to lexicographical rules "apple" > "app", because 'l' > '∅', where '∅' is defined as the blank character which is less than any other character (More info).

思路

本题使用 hashmap 记录每一个字母的相对大小，之后使用嵌套的 for 循环将 word 的每一个字符修改成字符的相对大小。最后使用 is_sorted 函数判断顺序即可。
时间复杂度 O(ns)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool isAlienSorted(vector<string>& words, string order) {
        unordered_map<char, int> orders;
        for(int i = 0; i < order.length(); i++){
            orders[order[i] - 'a'] = i;
        }
        for(auto &word: words){
            for(auto &c: word){
                c = orders[c - 'a'];
            }
        }
        return is_sorted(words.begin(), words.end());
    }
};

BTW，今天晚上看到一个很有意思的视频。

某种程度上说，我们都是推着巨石的西西弗斯。
,
  1. 3 月 16 日 每日一题
    1. 题目：953. Verifying an Alien Dictionary
    2. 思路
    3. 代码