查看: 3823|回复: 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;+ y0 V# _( x3 T# J2 B
}' D: K. Z# L+ q2 Q/ B
for (int i = 0; i < words.size() - 1; i++)
7 T' ~! I5 h9 [7 x$ I. Q {
0 i# d  j1 R0 G6 A2 I if (!check(words, words[i + 1], letter_orders)): N8 L& l1 H+ [. s" h
return false;
+ X5 r% E& n- P }
/ y) Q# x, ]' ^3 ?& s return true;
, z/ G: X+ ^$ l4 i9 h0 \3 m) E4 ~ }
7 c4 v) x$ q+ v: @ bool check(string a, string b, map<char, int>letter_orders)$ U, G, H8 c6 @# x2 [9 \
{
) e' t6 h3 g/ y  g4 Q int sign = -1;
7 L1 a! T  T  W3 L1 S for (int i = 0; i < a.length(); i++)
4 d1 d6 y" _6 w, f) R2 U  d3 ~ {( m5 F4 }' C2 L- z
if (letter_orders[a] < letter_orders[b])
  h. @+ C5 y: B/ R( Y9 O {& O) Y, M  N# P/ ?
return true;
5 u- |4 t& h+ `1 a }
6 [/ g9 q0 L, F- v else if (letter_orders[a] > letter_orders[b])6 c5 @3 t" G$ r7 }2 s
{
" S2 K, y4 j8 d& C% v" p1 f9 j& g return false;
5 q+ h6 w: @( B; C- ]: k }  @1 d# U, \# Z
}
3 Z2 N0 `5 S; w; d* J& ^4 H6 w return true;1 Z) P% M* `) t# [
}9 |' G8 V: ^$ H. C" B3 K& h5 X. h
};5 u. p% O+ m" n0 k2 J6 U
---------------------
: B: t6 i) n5 [% q. I* j( ~/ M1 U: J1 V

" m( Q: l- v( ~1 U" ?" U/ t- x0 P$ ?! v" a; }& B9 l
$ r4 b- o' S1 E9 d' _