题目描述
给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。 这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。
Example 1:
输入: pattern = “abba”, str = “dog cat cat dog” 输出: true
Example 2:
输入:pattern = “abba”, str = “dog cat cat fish” 输出: false
Example 3:
输入: pattern = “aaaa”, str = “dog cat cat dog” 输出: false
Example 4:
输入: pattern = “abba”, str = “dog dog dog dog” 输出: false
Constraints:
- 你可以假设 pattern 只包含小写字母， str 包含了由单个空格分隔的小写字母。
解题思路
- 使用两个map互相映射
C++代码
class Solution {
public:
bool wordPattern(string pattern, string s) {
unordered_map<string, char> str2ch;
unordered_map<char, string> ch2str;
int i = 0;
int size = s.size();
for(auto& ch : pattern){
if(i >= size){
return false;
}
int j = i;
while(j < size && s[j] != ' '){
j++;
}
string temp = s.substr(i, j - i);
if(str2ch.count(temp) && str2ch[temp] != ch){
return false;
}
if(ch2str.count(ch) && ch2str[ch] != temp){
return false;
}
str2ch[temp] = ch;
ch2str[ch] = temp;
i = j + 1;
}
return i >= size;
}
};
