290. Word Pattern
Given a pattern and a string str, find if str follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.
Examples:
-
pattern =
"abba", str ="dog cat cat dog"should return true. -
pattern =
"abba", str ="dog cat cat fish"should return false. -
pattern =
"aaaa", str ="dog cat cat dog"should return false. -
pattern =
"abba", str ="dog dog dog dog"should return false.
Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.
思路：
1.将源字符串分割存入vector中。
2.使用2个map来存对应的键值对。map1<char,string>,map2<string,char>
3.遍历字符串数组，然后比较插入到map中。直到找到不符合条件的return false.
代码如下：
1.map版
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
class
Solution {
public
:
vector<string> stringSplit(string s,
const
char
* split)
{
vector<string> result;
const
int
sLen = s.length();
char
*cs =
new
char
[sLen + 1];
strcpy
(cs, s.data());
char
*p;
p =
strtok
(cs, split);
while
(p)
{
printf
(
"%s\n"
, p);
string tmp(p);
result.push_back(tmp);
p =
strtok
(NULL, split);
}
return
result;
}
bool
wordPattern(string pattern, string str) {
const
char
* split =
" "
;
vector<string > strVector = stringSplit(str, split);
if
(pattern.length() != strVector.size())
return
false
;
map<
char
, string> mymap;
map<string,
char
> mymap2;
for
(
int
i = 0; i < pattern.length(); i++)
{
if
(mymap.find(pattern[i]) == mymap.end() && mymap2.find(strVector[i]) == mymap2.end())
{
mymap.insert(pair<
char
, string>(pattern[i], strVector[i]));
mymap2.insert(pair<string,
char
>(strVector[i], pattern[i]));
}
else
{
if
((
strcmp
(mymap[pattern[i]].data(), strVector[i].data()) != 0) ||
( mymap2[strVector[i]] != pattern[i]) )
{
return
false
;
}
}
}
return
true
;
}
};
|
2.unordered map版
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
bool
wordPattern(string pattern, string str) {
unordered_map<
char
, string> map;
unordered_map<string,
char
> map2;
vector<string> vec;
int
j = 0;
for
(
int
i = 0; i<str.size(); i++){
if
(str[i] ==
' '
){
string tmp = str.substr(j, i - j);
vec.push_back(tmp);
j = i + 1;
}
if
(i == str.size() - 1){
string tmp = str.substr(j, i - j + 1);
vec.push_back(tmp);
}
}
if
(pattern.size() != vec.size())
return
false
;
for
(
int
i = 0; i<pattern.size(); i++){
if
(map.find(pattern[i]) == map.end() && map2.find(vec[i]) == map2.end()){
map.insert(make_pair(pattern[i], vec[i]));
map2.insert(make_pair(vec[i], pattern[i]));
}
else
if
(map[pattern[i]] != vec[i] || map2[vec[i]] != pattern[i])
{
return
false
;
}
}
return
true
;
}
|
最后记录一下unordered_map与map的区别：
1、boost::unordered_map， 它与 stl::map的区别就是，stl::map是按照operator<比较判断元素是否相同，以及比较元素的大小，然后选择合适的位置插入到树中。所以，如果对map进行遍历（中序遍历）的话，输出的结果是有序的。顺序就是按照operator< 定义的大小排序。而boost::unordered_map是计算元素的Hash值，根据Hash值判断元素是否相同。所以，对unordered_map进行遍历，结果是无序的。
2、用法的区别就是，stl::map 的key需要定义operator< 。 而boost::unordered_map需要定义hash_value函数并且重载operator==。对于内置类型，如string，这些都不用操心。对于自定义的类型做key，就需要自己重载operator< 或者hash_value()了。
本文转自313119992 51CTO博客，原文链接:http://blog.51cto.com/qiaopeng688/1836427
