数学建模社区-数学中国
标题:
953. 验证外星语词典
[打印本页]
作者:
杨利霞
时间:
2019-4-19 21:45
标题:
953. 验证外星语词典
953. 验证外星语词典
- j6 W8 M+ B' r) E, G5 O7 g
# Y1 c! G7 {$ }& _1 h
解题思路：根据题目要求，比较两个相邻字母是否按照order排序；创建（map）letter_orders，记录字典顺序；
+ X' p2 k0 `! n1 P
比较即可
' F; f; Y6 R, ]) v- v
/ ]7 ~! m* Y3 {6 o
class Solution {
' t* ~0 u/ t+ F# f4 G. k2 k
public:
3 |0 x: y1 g; X: X; j0 L9 s: e
bool isAlienSorted(vector<string>& words, string order)
1 `' u$ X1 ]- Q7 @! C h |0 o
{
7 B$ i& t' R7 M
int min_letter_length = words[0].length();
# C9 e6 ^; S4 q
map<char, int> letter_orders;
, U: z1 M& J4 w5 t+ k H; G
letter_orders[' '] = 0;//空字符比其他字符都小记为0
|. a2 _, k& V. I% w$ f% B, \- U
for (int i = 0; i < order.length(); i++)
& g* T- n, A8 c
{
2 d3 Y$ [, o) F, K. ^
letter_orders[order
] = i + 1;
7 w3 j; z5 y( x9 \6 q* Y
}
8 J {$ U" }/ p: I
for (int i = 0; i < words.size() - 1; i++)
. d" s( N7 I C
{
6 k4 o' I' i+ [5 K- Z
if (!check(words
, words[i + 1], letter_orders))
( P8 X" q: S* x% _, M" s
return false;
% ~5 M# i& }: l: ]6 A; F+ f
}
- s. |1 _- Z, N6 _. L; z
return true;
4 [/ G0 N# J4 h' ~, Q* w' F. c$ c
}
. N9 j8 t* Q: E% J. b) x8 z' F; \9 ?6 G
bool check(string a, string b, map<char, int>letter_orders)
' J, ~- C, l3 P- X- Z$ w
{
/ c/ F. e$ E* [7 \
int sign = -1;
3 r9 L8 B1 o) ~/ l$ B& i% V) L
for (int i = 0; i < a.length(); i++)
+ p( G. n9 T5 j& V2 o. H) P
{
3 N! Y- i3 l/ [# R- f! m
if (letter_orders[a
] < letter_orders[b
])
+ N. i+ v. B" ~+ v1 `5 {9 U% B
{
9 n9 ^% w$ Z7 ?8 `
return true;
' m" w. d# f" K) a0 P) Q' w
}
' U% U% I5 b) W
else if (letter_orders[a
] > letter_orders[b
])
7 O. i, r* N) R' v
{
: v; D: }8 G$ I$ l# J
return false;
. a4 W; _8 [$ s1 \
}
' G) h& P* l9 q4 Q" _
}
# K0 N. g# A2 d! D6 I0 I
return true;
/ i* Z$ Q' U8 V9 }* {! U
}
, ?( f4 F- y7 {, e& V ~
};
~( {) U5 X0 e* _! S& L0 G
---------------------
; S' Y/ Q1 g: T& Q2 f
- {; Q4 P' D4 t: c; y+ l
6 Z* e' _& i( M C& |& L
A) F0 v+ c7 C+ G g+ U
% q6 z* x# a6 c/ G4 z* Y
作者:
3297325025
时间:
2019-4-23 23:55
你好可以请问一下order排序是自己设计吗，还有数据库从哪里找
2 ]6 J* l8 g' V6 t/ d3 d5 \: w
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
2 ]6 J* l8 g' V6 t/ d3 d5 \: w