作者：小秋秋 | 来源：互联网 | 2023-10-11 14:48
题目描述:（链接）Givenapatternandastringstr,findifstrfollowsthesamepattern.Herefollowmeansafullmat
题目描述:（链接）
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.
解题思路：
找到字符和字符串之间的映射关系就行了，用两个哈希表分别存放<字符，字符串>和<字符串, 字符>的映射关系，前提需要分解字符串(split函数)。
1 class Solution {
2 public:
3 bool wordPattern(string pattern, string str) {
4 unordered_map<char, string> cache1;
5 unordered_map<string, char> cache2;
6
7 vector<string> splitStrs = split(str, ‘ ‘);
8
9 if (splitStrs.size() != pattern.size()) {
10 return false;
11 }
12
13 for (size_t i = 0; i i) {
14 if (cache1.find(pattern[i]) == cache1.end() && cache2.find(splitStrs[i]) == cache2.end()) {
15 cache1[pattern[i]] = splitStrs[i];
16 cache2[splitStrs[i]] = pattern[i];
17 } else if (cache1.find(pattern[i]) != cache1.end() && cache2.find(splitStrs[i]) != cache2.end()){
18 if (cache1[pattern[i]] != splitStrs[i] && cache2[splitStrs[i]] != pattern[i]) {
19 return false;
20 }
21 } else {
22 return false;
23 }
24 }
25
26 return true;
27 }
28 private:
29 vector<string> split(const string& src, char sep) {
30 vector<string> result;
31 size_t lastIndex = 0;
32 size_t index = 0;
33 while ((index = src.find(sep, lastIndex)) != string::npos) {
34 result.push_back(src.substr(lastIndex, index - lastIndex));
35 lastIndex = index + 1;
36 }
37
38 string lastStr = src.substr(lastIndex);
39 if (!lastStr.empty()) {
40 result.push_back(lastStr);
41 }
42
43 return result;
44 }
45 };
京公网安备 11010802041100号