数学建模社区-数学中国
标题:
953. 验证外星语词典
[打印本页]
作者:
杨利霞
时间:
2019-4-19 21:45
标题:
953. 验证外星语词典
953. 验证外星语词典
8 A3 P4 ^+ a# P: @$ j
/ P- |: v2 o" j w/ Q b
解题思路:根据题目要求,比较两个相邻字母是否按照order排序;创建(map)letter_orders,记录字典顺序;
4 B1 c n5 W% C0 G% @7 y1 m
比较即可
8 H0 L$ [! M6 J. x8 r& e# [0 U' v
" t$ N* [* r8 Z8 r% P. q
class Solution {
* F) K: j+ M9 g4 Y
public:
. f# P/ C8 v) R& o( A
bool isAlienSorted(vector<string>& words, string order)
$ j( h0 I9 ^3 |+ q, o) ~
{
4 `4 q7 q& ]" S
int min_letter_length = words[0].length();
7 y2 _1 ~* T$ I- V" ~; M
map<char, int> letter_orders;
! d* L8 |$ V$ g" o$ j0 ~1 f
letter_orders[' '] = 0;//空字符比其他字符都小记为0
+ V0 z7 y+ H5 o
for (int i = 0; i < order.length(); i++)
0 L* m( ~' o8 s, f( b6 I1 l7 J
{
" u! J! o- N H' v! H2 J) s% K
letter_orders[order
] = i + 1;
2 R: D9 Y0 K) x
}
/ l, ^3 B7 i( E' B- s0 B
for (int i = 0; i < words.size() - 1; i++)
: b+ L2 j- w& K+ ^
{
9 w+ @1 J) u4 H: r5 X- v
if (!check(words
, words[i + 1], letter_orders))
3 ~* c3 p) Z* F: v& `& v
return false;
( P3 t& s7 v& z
}
& \! _; L9 X8 K6 ]- r
return true;
$ l- W: S/ u) ]7 K# O1 j
}
1 L5 h& P$ S$ O7 x( e( H
bool check(string a, string b, map<char, int>letter_orders)
1 ]2 i7 ^# o8 R
{
2 b q4 {) E: u
int sign = -1;
1 M& |4 e' `0 s/ e: y
for (int i = 0; i < a.length(); i++)
' c: O( _0 j5 t- g' }* F: o
{
$ }. X+ u# y5 Y% ?
if (letter_orders[a
] < letter_orders[b
])
, f+ f# X; T* r$ p4 A
{
5 B9 E L1 C* J
return true;
8 b+ R! \! J3 a2 d+ c2 |* Z
}
/ U8 x. G( [/ l9 n* z* T) I$ ^8 @
else if (letter_orders[a
] > letter_orders[b
])
! E. Z$ U# K& h* d7 z# V! ^
{
- D# ~3 u; J! A' l$ Q% C$ p
return false;
- j8 I) b( H" I; Z* v) b( b+ ~
}
2 X d0 i- i* |
}
- ^/ P- \1 a: e6 j$ @; H7 y
return true;
' ^' ]2 g/ }) X2 m" K! I+ q
}
6 o g5 u2 c# B' _) l* D0 G; ~
};
' ]- N/ j0 l- Z$ t0 X* k
---------------------
2 C/ e( a4 ^# }7 H9 k
: c( \* q0 L. T/ F, O3 [8 X! w$ i
7 ^* X W( a' q& A& L, ?8 [
) \4 |$ j6 K) {; {
- I2 r& i) w# _8 Z! h$ i. x1 x
作者:
3297325025
时间:
2019-4-23 23:55
你好可以请问一下order排序是自己设计吗,还有数据库从哪里找
6 h$ x: }; Y6 _! p
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5