查看: 3859|回复: 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;+ W# R/ M  B7 ?1 Q0 j
}/ W2 L; {6 A! S
for (int i = 0; i < words.size() - 1; i++)
% }/ A  g: ?0 @# N; ^: a- C  V {, _5 x, ?' N' i5 C
if (!check(words, words[i + 1], letter_orders))
3 i; U4 n$ M% B return false;
0 L$ }8 r* |5 O# h) b) C+ Q3 T }
, [! P% ]- S: `/ P return true;0 h$ r; e. E' B+ A
}
( ^3 B2 v, ^' g1 \, U! Q* R bool check(string a, string b, map<char, int>letter_orders)6 Q' A9 f# W- T) x  W
{' Z( @% B" m: e# q
int sign = -1;
: c' c) F2 K# q, A( J0 {5 s* W8 p for (int i = 0; i < a.length(); i++)  o5 |4 e' _, h3 D2 U
{
* ^- |; B9 o, O  a; R if (letter_orders[a] < letter_orders[b])
3 c9 P; ]/ e# S, E {
& S% B& A. Y5 F1 K1 V' h5 V4 `3 b return true;
: i  i  t( g, w+ r8 } }% x& O: Q1 d" v7 F
else if (letter_orders[a] > letter_orders[b])) g2 @9 u* @/ F, [) ~3 K
{
8 b' Z1 Y# T3 b return false;8 H" o- ?; |/ ]! d+ h, |! O
}
1 V! E9 x. m/ A; z1 S3 T }
9 K2 ^8 _2 N' ^( j8 w# w6 L; f return true;; f( E* e! @+ v+ R
}6 o+ \+ J- O7 X# E. H) h% y
};, v, N% _6 u, C, {4 f: I$ J
---------------------
8 Z2 S6 n" R& }: l3 O( |" X2 F
1 R) Y7 R1 ^( h- b0 Y( ]! w% T# L- N7 W/ w$ I) A0 T7 [
- i3 f3 n2 q8 h

3 ^& H/ R6 U, K  s, W