数学建模社区-数学中国
标题:
953. 验证外星语词典
[打印本页]
作者:
杨利霞
时间:
2019-4-19 21:45
标题:
953. 验证外星语词典
953. 验证外星语词典
3 G5 R0 }6 l' J0 D
+ p. D% |1 t) S6 S2 k9 w
解题思路:根据题目要求,比较两个相邻字母是否按照order排序;创建(map)letter_orders,记录字典顺序;
0 F, C: r: Y, y: G! z
比较即可
( B$ r) k4 [% D9 E0 g% g6 H
7 X" ^, R# X; q! x4 n
class Solution {
1 q9 {$ m5 }( e1 [8 @
public:
) N* Y% p; c% i7 Q% m0 e
bool isAlienSorted(vector<string>& words, string order)
/ Y; Z* ?8 f. A, R" e2 b$ W
{
" I* O$ ~2 h( C, g H4 m
int min_letter_length = words[0].length();
/ a. o7 G! N8 X2 f/ h5 N2 N
map<char, int> letter_orders;
0 N. }5 v& K3 A+ o* U6 e; ?
letter_orders[' '] = 0;//空字符比其他字符都小记为0
) q" C' \9 I; C+ t" w8 Z" |$ @
for (int i = 0; i < order.length(); i++)
f" E" q+ _- ^' ?
{
% u+ H# [7 u. s1 q7 `7 Y
letter_orders[order
] = i + 1;
2 x2 Q. M0 ~6 m/ @
}
4 ]( A# b" S. k1 v; a2 o n' v
for (int i = 0; i < words.size() - 1; i++)
' Y7 f. g9 @) y
{
% ?" [4 p, Q# `" p% d; L8 k& s
if (!check(words
, words[i + 1], letter_orders))
( H9 n+ {0 v& D4 F$ j
return false;
g8 B/ f6 E- U
}
1 M& P* I5 d7 M n4 i4 p
return true;
I. p& c7 k) a6 i. O; l
}
) g0 \. q. ?# s# M* U( Z
bool check(string a, string b, map<char, int>letter_orders)
+ _, G5 z8 L( u7 f; j4 x6 Q7 R
{
) ^1 I0 P5 T2 y% t: F8 C: m% e+ l
int sign = -1;
/ K& j3 s2 ?) v; S, D. H
for (int i = 0; i < a.length(); i++)
2 [: l7 j/ Y g1 ~6 ?* X" X
{
$ C7 q. I) S, v% o
if (letter_orders[a
] < letter_orders[b
])
% o9 s! g. U n# B- l# @1 x+ Z
{
/ S& i) b- ^/ g. U" I7 u; _
return true;
8 V3 ~/ z1 b) G$ t# B; o! q( s. z
}
@9 v4 v% c& E, o6 T a4 N
else if (letter_orders[a
] > letter_orders[b
])
$ r! {& \4 C+ e5 i
{
7 a6 _! W7 Y" A0 Z2 Y$ o+ ]' X
return false;
) ~. i/ |- }2 I. S: D3 v
}
- X5 y# j# [( o3 l
}
, b. f' `8 S L* {+ a, B. u
return true;
# p4 @2 d. G6 u' @& \
}
8 |0 I+ ^: q1 W: ]9 ]
};
" S( Y3 I! s: I! R
---------------------
2 v% m; m \! \0 A8 R
4 \$ p }' C# a* X; v+ H
( a- N) T3 N }% X7 C
! f2 I8 ^5 T8 G9 Q
. A- U5 {9 H7 N7 S! Q
作者:
3297325025
时间:
2019-4-23 23:55
你好可以请问一下order排序是自己设计吗,还有数据库从哪里找
% @# ?7 O; l2 f3 V9 q$ B" y9 N
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5