查看: 3842|回复: 1

953. 验证外星语词典

字体大小: 正常放大

杨利霞

5273 主题	82 听众	17万积分

TA的每日心情

	开心 2021-8-11 17:59

签到天数: 17 天

[LV.4]偶尔看看III

网络挑战赛参赛者

自我介绍: 本人女，毕业于内蒙古科技大学，担任文职专业，毕业专业英语。

群组: 2018美赛大象算法课程

群组: 2018美赛护航培训课程

群组: 2019年数学中国站长建

群组: 2019年数据分析师课程

群组: 2018年大象老师国赛优

电梯直达

1^#

发表于 2019-4-19 21:45 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

953. 验证外星语词典

解题思路：根据题目要求，比较两个相邻字母是否按照order排序；创建（map）letter_orders，记录字典顺序；
比较即可

class Solution {
public:
bool isAlienSorted(vector<string>& words, string order)
{
int min_letter_length = words[0].length();
map<char, int> letter_orders;
letter_orders[' '] = 0;//空字符比其他字符都小记为0
for (int i = 0; i < order.length(); i++)
{
letter_orders[order] = i + 1;+ g7 D( V( u+ N4 T; q
}, _( Y6 o* ~2 W4 g  S/ }
for (int i = 0; i < words.size() - 1; i++)
7 d9 J7 M$ h" f% Y& Z {0 R5 i& V0 ]& [' T; u- Q% c
if (!check(words, words[i + 1], letter_orders))- P3 x: f/ i+ x$ m4 f  X! i( n
return false;
4 Y5 h9 h  k: H8 F% i" J+ ]7 k }
' q5 O+ M. z+ f, V return true;
* H% ]1 q1 i* {- w  H- C; ] }2 o$ n% O* l" ~& _" x; I
bool check(string a, string b, map<char, int>letter_orders)
& j9 T6 p, ]4 d+ J2 E' m- c4 ^- h {
* _& H" f; W. q, B; T, L int sign = -1;
# ]/ f1 H+ c3 ^1 R for (int i = 0; i < a.length(); i++)
& o# s% d- d+ M% g& d2 X6 n {
* d: L" n# Z! V9 x- _ if (letter_orders[a] < letter_orders[b])  k% F: S$ r4 d' I8 t
{
' q) e" {* W9 k0 ]' W7 W( b return true;4 a* d1 h4 s# q3 `
}& P. L( T  |7 c+ k) X
else if (letter_orders[a] > letter_orders[b])/ v2 p4 ^- I) D$ E; A5 I  ^# f
{
% ]7 v( C9 t" L# X& L/ ~/ R return false;
# i* m- X8 w5 Y' T8 Y/ V' Q9 _9 ] }& Y' J7 Z4 D" x) Z
}
% X5 o' x) K+ {! V: Z+ e return true;
. A1 u0 c$ Q( k }' `4 K% N! Q+ P8 Z0 o2 l/ a
};3 i8 R* O" ?  M  f  X4 r4 t
--------------------- ( I9 S2 \) `3 h
, g  {, a: S3 t* N9 C. ~
( y7 z3 }; ?8 n: k- d* h) ]

# r/ t  e' s, {  K' ~6 P1 r
, ]5 e2 D# ?1 c8 P1 g" ?. x