查看: 3886|回复: 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;2 m/ j: x: S& n7 |- k( m  }
}
$ b4 o' a* _, N  k7 S, ?& W for (int i = 0; i < words.size() - 1; i++)
/ z" A  B) Y3 |: Y0 I- C7 q" n {
7 d2 S& o' {% E8 [! Z$ ^1 L& f if (!check(words, words[i + 1], letter_orders))
/ ^% K  L% a  C3 f7 d return false;
6 o7 G1 |, ^# k8 f }0 O$ ^5 P+ I2 X/ ]2 V) b9 h
return true;$ B8 i2 d9 W' y5 w
}
1 n( J# N, C2 `8 B; B bool check(string a, string b, map<char, int>letter_orders)  T7 e7 m& f5 F' @% [/ q
{
+ I. ^7 Y/ ?6 Y. o; s; Z int sign = -1;$ Y9 c4 k( z9 i9 s2 J
for (int i = 0; i < a.length(); i++)2 ]& A" E' S& L1 r6 f2 S
{# }* J. |8 ^! ~9 m$ Z. u
if (letter_orders[a] < letter_orders[b])+ `6 ^6 B5 ]6 e' g2 Q
{
9 g$ L8 h& R2 {' ]/ ~( G return true;+ b& p# ]9 b) _% b: B  o
}! q) A# ]  x  Q
else if (letter_orders[a] > letter_orders[b])2 d2 A) q0 x/ ]3 D6 p6 ~/ \
{
0 t. B; f9 {/ o5 B) s return false;
: f+ f( h9 e! r4 M1 P' }9 @5 D }( ?3 q* T+ R8 d$ b) z- v
}% d6 d% ]; Z( a7 j5 |: Q1 a! P
return true;# h% b$ G2 J" \* k; M2 g/ ]5 T
}, S3 k8 i0 E1 Q  \
};
2 a( Z" \+ p% Y! Z; I3 T9 g---------------------
9 k9 H! i7 Y0 t6 o& U1 N+ ~, }" h0 f* k: z0 s/ ^
/ P5 M, m& o. z9 Q, W
( e0 x2 _- X2 ]1 B2 {

& }; |- P* M/ z1 h: t( j% W7 B