查看: 3838|回复: 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;
) y/ ^' K4 I' J- d* g* p9 r+ _ }( j4 f7 H( S( X7 R2 M0 \0 H. H* z
for (int i = 0; i < words.size() - 1; i++)
* {9 k; i$ a# ]) k {
3 E7 g7 |1 S+ i; @- ? if (!check(words, words[i + 1], letter_orders))
/ i+ |; \* m1 q! N  d6 Z return false;
$ D$ R  F9 E" y9 z- T) j }
" a5 V6 p" L2 U9 \1 A5 [, [ return true;
: X6 A9 n$ j- y0 n2 c+ M# X2 K }  ?/ t/ m3 |* V0 ?" k1 n. V7 H
bool check(string a, string b, map<char, int>letter_orders)/ i: w" ]! p- F
{: v+ Y0 R3 l' H# T  v
int sign = -1;2 H+ Z3 T! L; }: m7 J8 z. y
for (int i = 0; i < a.length(); i++)5 E! [- P; ~& Q8 C) ^9 x1 V6 m
{
' ~- p, c3 t/ u if (letter_orders[a] < letter_orders[b])
; E; }' P) A/ J6 }5 p {
: U  r; X' K' A* c; ]4 P6 g" ~ return true;
# N7 D1 `- s5 t! H7 w) w }9 p! W, G4 _8 ?6 C" o
else if (letter_orders[a] > letter_orders[b])0 m/ ~! g, A% T; D# G9 i
{
1 A2 x: i/ S( M- j! a return false;
1 R( k. R3 p( E6 y }
0 E/ l& N) G( s }4 g) x4 U& Q' L. a3 Z) l
return true;4 o+ p+ ^0 T5 T* q0 @  l2 k1 B: V- s
}
/ j' }0 N8 @% [/ x};
% T0 a' k& ~, S( T  j--------------------- ; s- B" q  n5 c# H

6 @/ C0 m# }5 b0 C( o$ E# P
3 Z% |8 t# w# n/ I. z! b7 }' \: S# S, @* w8 V* w6 X& y9 d

1 q( X7 c. p# G+ A/ g