分享程序员开发的那些事...
更新时间：2022-10-02 22:52:39
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