本文最后更新于：2021年1月15日 晚上
给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。
这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。
示例1:
| 输入: pattern = "abba", str = "dog cat cat dog"
输出: true
|
示例 2:
| 输入:pattern = "abba", str = "dog cat cat fish"
输出: false
|
示例 3:
| 输入: pattern = "aaaa", str = "dog cat cat dog"
输出: false
|
示例 4:
| 输入: pattern = "abba", str = "dog dog dog dog"
输出: false
|
说明:
你可以假设 pattern 只包含小写字母， str 包含了由单个空格分隔的小写字母。
Solution
参考 @treasure_ 、**@heroding**
建立char->string的哈希表，如果char(key)，没出现过，则赋值为string(value)，如果出现过，则比较value与当前string是否一样，不一样则返回false。
这样做只会忽略一种情况：abba; dog,dog,dog,dog; 这时候由于a和b的对应value都相同，所以会误判为true，所以再反向hash一次，建立string->char的哈希表，两次hash遍历中都没有return false的才返回true。
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
|
class Solution {
public:
bool wordPattern(string pattern, string s) {
unordered_map<char, string> ch2str;
unordered_map<string, char> str2ch;
vector<string> word = split(s, ' ');
if(pattern.size() != word.size())
return false;
for(int i=0; i<pattern.size(); ++i){
if(ch2str.find(pattern[i]) != ch2str.end() && ch2str[pattern[i]] != word[i])
return false;
if(str2ch.find(word[i]) != str2ch.end() && str2ch[word[i]] != pattern[i])
return false;
ch2str[pattern[i]] = word[i];
str2ch[word[i]] = pattern[i];
}
return true;
}
private:
vector<string> split(string s, char c){
vector<string> res;
string ss;
for(int i=0; i<s.size(); ++i){
if(s[i]==c){
if(ss.size())
res.push_back(ss);
ss="";
}
else
ss+=s[i];
}
if(ss.size())
res.push_back(ss);
return res;
}
};
|