剑指 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;
}
};
相关文章
- 选择排序 c语言(链表法)「建议收藏」
- (c语言)选择排序法和冒泡排序法
- c语言实现fastcgi
- 快速排序(Java语言实现)
- 使用jna调用c语言动态库对接华视电子身份证阅读机
- python用冒泡法排序_数组冒泡排序c语言函数
- C语言-链表排序_单链表的排序c语言
- 对成绩进行排序c语言_c语言对学生成绩进行排序
- 分页式虚拟存储管理_c语言申请内存空间
- R语言卡方检验方法总结
- GoLang15 - Go语言范围(Range)
- Java真的是一门编译型的语言吗——即时编译器JIT
- 使用Go语言调用OpenAI API
- 跟着Nature Communications学数据分析:R语言做随机森林模型并对变量重要性排序
- Skill语言实现将一个table中的坐标point(x,y)按照x和y进行从小到大排序的函数
- 【C 语言】二级指针作为输入 ( 指针数组 | 指针数组排序 | 字符串排序 | strcmp 函数 )
- 【C 语言】二级指针作为输入 ( 自定义二级指针内存 | 二级指针排序 | 抽象业务逻辑函数 )
- 【C 语言】二级指针内存模型 ( 指针数组 | 二维数组 | 自定义二级指针 | 将 一、二 模型数据拷贝到 三 模型中 并 排序 )
- 基于重排序的新量化方法RPTQ:实现大型语言模型的 3 比特量化
- Go语言多维数组简述
- C++语言的历史
- Go语言结构体字面量
- 在 Fedora 上开启 Go 语言之旅
- Linux之下编写C语言程序的试验记(linux c语言试题)
- c语言合并两个已排序数组的示例(c语言数组排序)