查看: 3818|回复: 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;
7 r: z1 |9 r, w$ Q5 X }
3 V4 o- `& f2 f( c# n9 U) r for (int i = 0; i < words.size() - 1; i++)
& e' x3 L- X/ _! V# n9 e# l, p) @ {
- E  ?, s1 d/ _- R: l, Z% g9 q if (!check(words, words[i + 1], letter_orders))
6 k1 G2 w8 X: V( S return false;
4 U+ q5 L( G1 i( f5 ]) h/ ? }
  g- v" G6 D6 W9 U/ A return true;" a/ m( [- |+ [+ D+ E# \* v
}" Z2 I: _7 Y( }; o/ f
bool check(string a, string b, map<char, int>letter_orders)+ ]& M% P* H2 E1 D
{) V( q0 [$ y6 V( R- S1 ^5 I5 o
int sign = -1;3 ]1 H8 d  P7 U/ q% v
for (int i = 0; i < a.length(); i++)2 s- K' e, J* W/ g2 |
{  a, E5 B: D" t! b% W' s
if (letter_orders[a] < letter_orders[b])
+ G) P2 E. r8 k" f& H% Q {
' u+ Z! t6 U" |3 M1 c0 I$ @ return true;6 O$ x0 ~  M) h/ K1 F0 m. m/ b
}. v+ |$ t. }3 C( ~' ~  _
else if (letter_orders[a] > letter_orders[b])) y  Z0 |! j3 ?3 g! A& L# q  V
{
  ~2 S* ^# y9 B! g return false;- E; K& J4 X; R# F6 G' F, d
}; l2 ?  k( n6 w& g! V
}
  P! B( ?0 B9 c. `( z7 V return true;
$ n9 R$ U2 x! A1 D }
( S! P7 z$ ?' o: n3 R  s/ P};, r6 }- _, m2 n, X3 }& ^/ y+ M
--------------------- 1 @! ?: }7 d3 m4 ~
4 E; I; |& T9 T7 Q' X3 K
6 l0 ]* `. J/ `0 Z

0 @+ R. @9 T2 u) P. ?, l
3 j* R8 Y, M5 p9 y$ u