查看: 3849|回复: 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;
* z2 z) z; c& ~8 B' j }4 }- Z# t% c4 Q
for (int i = 0; i < words.size() - 1; i++)$ C2 l- n, A  g4 D& r! y$ i
{# ~% r3 q/ i. G$ @1 V% b3 x
if (!check(words, words[i + 1], letter_orders))8 T0 k1 Q! h/ ^# a4 g
return false;
9 z% |2 o: P, b  { }
' \& f& _6 J1 t9 I% j return true;
. S1 K, Q/ W/ @* | }
7 ~2 V4 C2 Q3 ?, E) g# } bool check(string a, string b, map<char, int>letter_orders)
  M* F/ u. R$ Y% T4 ?/ S {
' d0 e% Q8 F; J- A! r* K9 }% f2 L int sign = -1;; V- d$ F1 B- D/ N
for (int i = 0; i < a.length(); i++)' O3 J* D' Z6 e0 P8 ^
{
' m" d- g4 }, r& T* ^& @ if (letter_orders[a] < letter_orders[b])! n8 `! d; i# M9 r9 G
{
  B4 Y# i& u: x% b8 C# E9 u return true;
" I8 O; P0 N/ r& ~8 G; P7 \ }
0 \" e7 \* j3 \- L& S2 p else if (letter_orders[a] > letter_orders[b])
# \$ W' p' ]" J- j- Y' A {4 c3 W) z" t$ F1 }. @4 f
return false;
2 n3 Y5 R' p1 W. u- U3 x3 V }
& W% ^# b3 p$ ]+ C% W }$ a0 T2 U- G  B' L0 X) }
return true;
4 t- j, j; K# k0 F3 E }
" e6 k9 m/ [2 L0 |};$ T& v/ [0 i' ~( [8 W
--------------------- " M! B1 |. o4 _* L7 b
" R/ W% Z6 m, n8 h& T* Y
2 }# [6 Q( s6 g, B4 R

; ~5 W0 Q0 ~1 \5 e5 d3 O1 v7 ~; I1 ^  v& e5 [6 q+ A; F