数学建模社区-数学中国
标题:
953. 验证外星语词典
[打印本页]
作者:
杨利霞
时间:
2019-4-19 21:45
标题:
953. 验证外星语词典
953. 验证外星语词典
; M, W! D! y+ ?' h9 _; Z5 S
7 @8 a& _; d3 f5 x( b3 t- O0 l
解题思路：根据题目要求，比较两个相邻字母是否按照order排序；创建（map）letter_orders，记录字典顺序；
8 G- W- N/ G( J" t- x$ m: z1 y
比较即可
( a) M5 o' R5 d/ q- V( l
/ b4 x; Y1 S0 G2 q4 Q
class Solution {
1 Y* w( I, }2 j, |' Q* z* Z2 A
public:
& f" M3 w+ }6 P" Y& u, O" _
bool isAlienSorted(vector<string>& words, string order)
# X& l* D" V6 H7 i$ W
{
( g: S! v+ E& N$ B1 |& S/ M
int min_letter_length = words[0].length();
' E, B) ]* ?/ {0 K3 \
map<char, int> letter_orders;
. y6 t& T6 l7 \3 ?3 E/ W5 n4 D7 d2 I
letter_orders[' '] = 0;//空字符比其他字符都小记为0
6 ]$ l* | h, z( Q. S
for (int i = 0; i < order.length(); i++)
; i' d4 Q( a0 E# x# w
{
6 S: Z ]" M P$ k( z
letter_orders[order
] = i + 1;
- ]5 s( {& {8 p+ a+ z
}
`8 v* A. `: Y# t3 M% M) O' ?
for (int i = 0; i < words.size() - 1; i++)
" I6 q. q1 Q: i
{
% F( V6 `. C) e8 V* Q4 k0 Y& a s3 M- G
if (!check(words
, words[i + 1], letter_orders))
- S v* t$ G( @% H' }, r
return false;
B0 f. V9 j: U% M: a
}
3 C) m& R: ]: @' {
return true;
7 Z( I4 v c: ]! e' k3 U/ @
}
2 q+ F. H/ F( n+ s
bool check(string a, string b, map<char, int>letter_orders)
/ [% a, }# l+ x; I8 M
{
7 H5 v$ r: T6 A6 e5 R! y$ i
int sign = -1;
2 J9 e! y9 E9 T/ K4 p$ C- _7 c
for (int i = 0; i < a.length(); i++)
3 w$ H6 a, \8 T: x$ I& d! D4 f9 v
{
. I4 J% R0 ^( o) h: X+ L
if (letter_orders[a
] < letter_orders[b
])
$ A3 ?" i+ i. o. X- H
{
4 g+ f; ^. C, H. T7 M8 D
return true;
* r+ D _4 t* t& D( F
}
, B( [( n+ a6 X$ n9 Y( n
else if (letter_orders[a
] > letter_orders[b
])
, j8 |6 a7 r( q b' ]) {
{
) }6 K# w& g9 f; }, N1 A
return false;
' ?9 j9 a) Q% P# V T9 b1 @" W! P
}
( X' k( ^0 h! ^, n+ L/ r
}
7 S5 R' F; }" v: C j* c
return true;
" T, E) f. V, x: I5 {; ~
}
( P4 K/ I! P5 Y+ l" H4 M- C
};
' `% ?) ~, {! _# f+ G; B+ S+ P# R
---------------------
; h& V! P4 b/ F6 n9 `! r$ k
# |5 f' T6 I8 O, d) @6 Z
6 e& y/ p6 ~( h
: m4 L# l5 m; _1 x" X
! b$ t3 d6 }2 i# d' v
作者:
3297325025
时间:
2019-4-23 23:55
你好可以请问一下order排序是自己设计吗，还有数据库从哪里找
$ N: z8 r6 x0 U! k3 E/ l
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
