查看: 3884|回复: 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;
  u- ^! x+ W; ?6 {' W2 S) X }
$ J. j6 Y( |( ^) a* x8 \, S for (int i = 0; i < words.size() - 1; i++)
+ X; P6 z7 w3 X+ ~3 n* D {5 ^" ?7 k$ H+ p& v
if (!check(words, words[i + 1], letter_orders))* {! G) `$ `; M" {1 {
return false;1 q1 S( h: f( d* @2 I% V
}2 b8 p: S4 V7 J1 c0 ]
return true;1 P" `; V0 Z; Z
}, m7 v1 a; P: K: k9 [6 D* y" V4 L
bool check(string a, string b, map<char, int>letter_orders)
# d; P1 M/ Y" _: O5 w {0 w* J" X  i8 W9 d5 O
int sign = -1;; X, q% ~. G* l" l# `
for (int i = 0; i < a.length(); i++)0 w" J% \; e+ E/ j0 V( B
{1 [# h2 {1 Z! N) R+ P, d6 b+ j1 P
if (letter_orders[a] < letter_orders[b])
: J5 w4 }2 n% Z" O8 Y {
0 L6 a( B6 G5 T3 A/ ? return true;
" w% h( d* a' z5 ~9 Z }* ]. {# Z! P3 }  c/ p+ s9 a+ }2 ]: J
else if (letter_orders[a] > letter_orders[b])7 a, H- o6 }) }2 J# t) r
{
7 ?. W6 B8 L8 m8 Q9 R( A. G& w return false;5 k" k* n$ M7 P$ s0 }9 j
}
1 p$ Y& J: e& L$ z. B$ y }, q4 r$ G: }+ s7 e6 U& k
return true;7 N4 u, p6 c, Q( F7 n% c, Q
}
+ r7 o, k  y, r9 @3 T};. T5 _7 l# Y/ c2 S4 `
---------------------
* a. M, j# C) U+ Q# [( R$ b* _
* s0 A( H% b/ {: g" C! R9 O
2 I; C" y& Q3 y$ v+ p* }7 w: ~9 I+ |0 U: i* Y+ `

* N4 N3 E" j: x" v2 c; m