数学建模社区-数学中国
标题:
953. 验证外星语词典
[打印本页]
作者:
杨利霞
时间:
2019-4-19 21:45
标题:
953. 验证外星语词典
953. 验证外星语词典
+ S5 u% {( Y; U: @( |" U
6 t2 u# E) P4 V4 S, D" _/ E
解题思路：根据题目要求，比较两个相邻字母是否按照order排序；创建（map）letter_orders，记录字典顺序；
! U, C5 k% s. y" C4 W; R
比较即可
8 H$ Q% v7 R M4 N3 P) f
( \9 k6 ]8 R( n! X- c; h
class Solution {
^5 I2 k/ o+ j7 K
public:
1 @% V B4 S( z4 y5 U
bool isAlienSorted(vector<string>& words, string order)
: A1 d! n$ _: P6 L* T
{
|, m$ j1 f4 y4 _2 v L
int min_letter_length = words[0].length();
- q& x/ g/ v( l) K$ N; J
map<char, int> letter_orders;
: D, `# w1 c+ C
letter_orders[' '] = 0;//空字符比其他字符都小记为0
3 Q( N8 d4 K# U/ r, R* h
for (int i = 0; i < order.length(); i++)
/ o% g, V J" [2 ~
{
/ c1 T6 E, R5 H% R: q
letter_orders[order
] = i + 1;
, q5 y& J7 R$ s. f
}
M5 B5 x! f) f
for (int i = 0; i < words.size() - 1; i++)
/ f R+ y4 A/ |5 P2 ]
{
6 A8 Q" T. s4 O0 j0 U' Y
if (!check(words
, words[i + 1], letter_orders))
) }" ]* V# y5 W: L* D, u' q% F1 f
return false;
7 I' G* }0 {7 x
}
r9 [( q* V( |
return true;
6 l( a. h0 o2 l
}
8 l$ s8 \3 c* N. o. G$ p4 D
bool check(string a, string b, map<char, int>letter_orders)
& y) _" x/ c3 a8 g; E: U! G; X
{
+ ]* H0 h5 G' R6 K
int sign = -1;
) d: v" A# F9 p2 N1 c! a
for (int i = 0; i < a.length(); i++)
) n8 K% f! Z& w! R3 P7 T+ s( I
{
4 M& S% `6 M$ T) k% U
if (letter_orders[a
] < letter_orders[b
])
9 L: F1 r. O3 K+ a$ @
{
, C% N, d- |) y7 _ W
return true;
3 X+ \8 k& W0 y" W" F/ p5 g$ j
}
3 \9 `. i7 I0 Y. H/ m
else if (letter_orders[a
] > letter_orders[b
])
9 G: ?! q; @- k7 D9 C/ S7 X
{
4 Q* T2 Q" T8 @
return false;
: ^$ `4 s6 x3 d# G5 [
}
7 j, V# [. `9 S* r
}
% i7 m/ |8 c5 g+ `/ ?6 \8 K
return true;
2 `. w' k) ~0 i( J$ T. C8 p+ V# w
}
5 _7 @3 Y' }% Q% S
};
* |* f& R1 p6 t$ d* N
---------------------
. S7 O3 J: r' x" p5 b2 [. }
$ w. ]# _1 d* ]8 w0 b
! V. s( q q) g' r1 s1 A
! w5 U: h9 d% t' P: N
+ }# x: w. z; G1 x) h
作者:
3297325025
时间:
2019-4-23 23:55
你好可以请问一下order排序是自己设计吗，还有数据库从哪里找
( A; e {3 h; P# U: G+ R0 q a- c) w6 A
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
( A; e {3 h; P# U: G+ R0 q a- c) w6 A