查看: 3862|回复: 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;
# ~8 U+ x# x% Y; [" [5 d }9 c! V7 W8 U. X  D
for (int i = 0; i < words.size() - 1; i++)& D9 w1 C+ ]& X3 r; B
{
. R* f; O8 B5 [) G! ^* p# k if (!check(words, words[i + 1], letter_orders))
4 w/ u( h2 m1 s, p+ _( A return false;
" s4 Q; [; n4 M5 B }2 I$ R! |! X. Y: |5 ]
return true;
" m* K4 {! h5 g. ]6 q: z; B1 U }
: ^. ?3 N% H& Z% i1 o bool check(string a, string b, map<char, int>letter_orders)
6 f+ _& b6 Y# v5 E- S8 ^8 t4 u {
% `% E! j8 z" \6 c# z int sign = -1;
& b; Y3 d3 `# c" U( Y4 X for (int i = 0; i < a.length(); i++)
' _/ j2 l9 w& r {
! ~' j+ [! Z: J; } if (letter_orders[a] < letter_orders[b])
( y' Z6 C' [; b& x7 W. O {
( L( q! `- q  }/ d return true;
6 Y. Z1 i  {; U. k, z }3 z0 X( k. N& ~9 W! {
else if (letter_orders[a] > letter_orders[b])
3 ~& t. Q; L" b  T) [ {3 g$ k/ F7 S% E4 I
return false;
% x' Q. I5 S7 R1 M& c4 t4 \/ O }
! H; _& D# i. }) M }
( F  u5 O" [0 z2 l& M9 e, Q return true;
+ j0 E  N9 ?2 l$ `# R }& b" s5 w) @/ _
};
0 ~* m, A6 Y6 l2 _# T9 {, w' T---------------------
7 U1 w; `( I/ O' A" G- d9 x% t. l, t9 V0 s

6 E2 W4 \% B5 Q6 I$ A
; g& D# v) v8 |" ~1 W  @4 ]7 V/ c5 {6 l) R