查看: 3140|回复: 1

953. 验证外星语词典

字体大小: 正常放大

杨利霞

5250 主题	81 听众	16万积分

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;
, H5 F' O; ]' J& o5 x }  R. n7 U1 j0 e  ]4 }+ Y
for (int i = 0; i < words.size() - 1; i++)
7 z4 s" f# R: H3 `# Z {& Y" x$ s$ i2 D/ |9 i: v7 b7 q
if (!check(words, words[i + 1], letter_orders))' q/ ^1 }  `* \8 {! R
return false;/ S; E/ _& {2 {- z5 t& [
}, }" L' B( X7 s0 t- C0 L. ^( W9 {" a4 r
return true;
$ D& T3 c7 V9 G$ b- Z6 L }
7 d# z& ]4 D- `  D5 J bool check(string a, string b, map<char, int>letter_orders)" ?) w) `. v0 A; v3 s+ u
{6 r; t! s3 Z; U( ]$ i
int sign = -1;
! G% V1 Z9 u1 u* G2 _; o$ u for (int i = 0; i < a.length(); i++)
; |$ ~: K; `# ?" R2 b4 r {
7 e  w' V0 l8 g/ p, U  Q if (letter_orders[a] < letter_orders[b]), x& c) K8 g* g9 m. }6 }: r
{' {2 y: X: o/ z. _; Q7 q
return true;' _" }3 b6 U) X7 Q
}
; T& B& J" ?- V1 M4 u, U else if (letter_orders[a] > letter_orders[b])
. C, c) r. Q- D/ [ {
  k* W. T( j) X' K; e return false;
0 @" E! A; J0 N% F: d2 N }2 E. K8 K$ ~5 G, v/ g# N7 T. K
}$ n* _& `, {  {
return true;
4 y# i: Y5 j  r9 N2 \. e( Q }
& r; s4 q' ?: I' i, q2 Y; x};4 r1 \) V' c& T( _
--------------------- 3 G9 y1 e5 B. t' i7 m, B
7 ^! c+ z1 @  n, g  i  C
. G  R: E% U* b2 z
7 |# R8 F* K" Q4 H2 \

5 h3 L9 [- `  z9 J