剑指 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 < = w o r d s . l e n g t h < = 100 1 <= words.length <= 100 1<=words.length<=100
- 1 < = w o r d s [ i ] . l e n g t h < = 20 1 <= words[i].length <= 20 1<=words[i].length<=20
- o r d e r . l e n g t h = = 26 order.length == 26 order.length==26
- 在
words[i]
和order
中的所有字符都是英文小写字母。
解法:哈希表
用哈希表 m
记录 order
到 a ~ z
得映射,比如 order = "hlabcdefgijkmnopqrstuvwxyz"
,那么 m['h'] = 'a' , m['i'] = 'b'
。
用 pre
表示上一个已经转换过的 word
,这时的word
代表当前 word
。我们先将当前的 word
根据 m
的映射进行转换。
如果 pre > word
,说明 words
不是按给定的字典序排序的,返回 false
。
遍历完成说明 words
是按照给定字典序排序的,那么返回 true
。
时间复杂度: O ( m ∗ n ) O(m * n) O(m∗n)
C 代码:
class Solution {
public:
bool isAlienSorted(vector<string>& words, string order) {
unordered_map<char,char> m;
for(int i = 0;i < order.size();i ){
m[order[i]] = i 'a';
}
string pre;
for(auto word:words){
int n = word.size();
for(int i = 0;i < n;i ){
word[i] = m[word[i]];
}
if(pre > word) return false;
pre = word;
}
return true;
}
};
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgagekh
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01