查看: 3865|回复: 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;
$ d- a1 m8 O+ q9 M/ j& X }
( H- [9 w" D( b for (int i = 0; i < words.size() - 1; i++)
# T. L# e+ f* h6 R+ z  x! h' \ {
/ {  [) I5 ]! t; e% x6 f if (!check(words, words[i + 1], letter_orders))" M0 y9 K  ~8 ]5 j9 O1 D
return false;2 r) J7 S7 X8 g% r9 @& y
}
& Y, G+ E* W# J8 d, A" Z3 c& N return true;
, J5 h+ c1 Q  s }
" H6 F0 T2 Q: ?" L bool check(string a, string b, map<char, int>letter_orders)* {; G- ]3 n3 [+ t
{
8 O. m8 G- O; q( I! q1 [# { int sign = -1;% [8 `/ F) {/ _  T, |
for (int i = 0; i < a.length(); i++)* T9 B1 Q0 T) d$ c  Y+ [0 N0 L. B
{
' P( v% q7 b" q$ o0 n& x if (letter_orders[a] < letter_orders[b])" W8 c( Z% ~- X* {
{
1 l9 S, q# X/ O) B0 g1 u3 n return true;9 G* t0 y/ J" g4 k
}
+ I' W- j8 E) f1 D+ B7 {2 ~. O9 X- U else if (letter_orders[a] > letter_orders[b])7 m  O9 z" e5 [# k" G7 N/ V
{
% X% S1 t2 C0 {1 X+ L return false;
% V6 D' i0 {9 O  t/ b( g  ~9 S8 U }
( J+ Z; @7 ?( U" I9 k }! t1 |' d; a! ]4 @
return true;
8 T; X; }4 I: I6 T3 [& r/ U* s! H* \ }
1 B! s- c# i) j+ ~( w};) B# p* W& k1 y, p( j( g+ g  W
---------------------
, W) p: o7 S4 C% b
+ q1 I4 [) ^: B2 @: r
7 s1 W2 @. H+ `5 v( I8 D) w" E, X; g; J& G3 u7 B, F

# k9 \0 z* f3 n1 N