查看: 3879|回复: 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;
% J$ l1 v1 f1 J  b& L }
: X3 ?) s" X! e- e for (int i = 0; i < words.size() - 1; i++)
8 A& a: \) J; O* H8 P: ]0 O: @ {
' B" X3 o" _( F/ t, s: n, g2 U if (!check(words, words[i + 1], letter_orders))
7 U  l, x1 e+ H. ?6 Y* ^1 o$ v return false;
8 a+ D* O* f" v7 L8 ?, L }, c9 o& k/ ~8 ?& }
return true;
- y3 Q& h" i( V/ v }
- |# ~6 X& c% T+ P# U6 L2 v bool check(string a, string b, map<char, int>letter_orders)7 @/ M; Y+ `/ O. c
{
5 w  C* t& ?5 i$ R- m3 Z int sign = -1;: x' R$ |+ f, E7 r# I) z! _  Z
for (int i = 0; i < a.length(); i++)
5 r( i5 v- b6 {/ E {9 S0 d6 t- K& c3 o' \4 y
if (letter_orders[a] < letter_orders[b]). L. @6 @0 ?: u+ a
{/ D7 n. k5 D, j: N) s6 z
return true;0 _* {& z0 x* m3 f/ A
}
( y1 ]' ?* V! P1 B4 f1 e else if (letter_orders[a] > letter_orders[b])- w: B8 Q7 F5 Y" Q- ^9 r; Y
{
4 X4 ^( J; J  o( \. `# c return false;
% x  ~* I. u/ M$ }2 o% I* k( Y }
; |  k# b# b' o' [ }/ L0 q$ c  J  ?/ V
return true;8 d5 k5 B7 G, r- ?+ H! e! y
}
& c4 C; M* m. @5 b9 B6 N};
! O* S8 Y$ G$ F5 ]) \, `---------------------
& G" b6 f5 e! I; }$ q1 w
& F6 H1 a* o' ?' m
+ \7 k- C- q) \% J. X) j$ ?) \) T! \* r; Q4 d' }* f& Y
7 h: A0 G% z2 a& W5 o1 F