查看: 3882|回复: 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;0 O! a; h+ X# V0 ?$ x
}* s. e' u& |' R' S/ W4 o
for (int i = 0; i < words.size() - 1; i++)0 ^7 X& {( Z* g4 D0 Y6 s, U; I
{5 }3 u' s. Q& x0 y6 X' h4 y
if (!check(words, words[i + 1], letter_orders))8 V  p/ p  E5 X6 Q! v: |
return false;3 @! f$ A4 x6 B1 A: v
}* ?; H& ]9 n; x
return true;8 Y( l' D7 a: Y9 ~
}  [" F, E2 I% B1 _
bool check(string a, string b, map<char, int>letter_orders)
/ ]4 N$ h- v% t" t$ T9 }$ [ {* |4 B4 f7 `; h, i, R5 R, R( h
int sign = -1;& U% L) [- L( f2 H! E
for (int i = 0; i < a.length(); i++)
/ h5 F& U0 X/ r' f6 r7 Z {
/ ?4 B, ]; h$ @+ m& K& N! X8 r0 e8 y if (letter_orders[a] < letter_orders[b])
; C5 Y" \! M% Q) l9 H% P$ A {
& K8 A$ A3 k1 c# T* Y8 Q3 f return true;8 x4 V, \$ {: W5 w: \# d8 ~
}0 Z- G+ s# L! O+ n, j  V) F
else if (letter_orders[a] > letter_orders[b])
  ?  R& D& Z7 X8 M" f) K9 g {% i* q% s' S3 H' ?. G% V6 L9 W( _
return false;
  c) @( C/ C. K1 w, A/ Z) B }
5 V8 k% {$ V# j1 i2 z' ^& M. } }
6 e1 K+ Q, X2 ~% e( Q return true;1 O! P6 ~' p6 t/ o1 b9 h
}
- D8 V- H6 K3 ~+ J8 x- h! d};$ G) M/ d4 e5 Z( _; V
--------------------- ; j# }# P* ]5 n5 y2 `) W7 {

0 x$ g6 |. ^) q# N" e
( _. K: a, d; v) w! o& g: A- `3 V5 M2 Q# n6 z) ^$ v
9 i$ Y- H: j2 O9 S