【LeetCode 290】单词规律
Problem Description
给定一种规律 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
思路
使用map映射,将每个单词与对应字母的映射关系保存起来,然后判断后面的单词与字母是否跟映射的保持一致,不一致则说明不匹配。
代码
class Solution {
public:
bool wordPattern(string pattern, string str) {
if(!pattern.length() || !str.length()){
return false;
}
map<string,char> m;//保存单词与字母的映射关系
int flag[26] = {0};
string word = "";
str += " ";
int index = 0;
for(int i = 0; i < str.length(); i++){
if(str[i] == ' '){
if(m.find(word) == m.end()){ //字符串中的单词没有出现过,那么就看pattern中对应的字母是否被用过
if(flag[pattern[index]-'a']){ //这个字母已经被用过了,则说明不匹配
return false;
}
m[word] = pattern[index];//没有用过,则将单词与字母进行map映射
flag[pattern[index]-'a'] = 1;//并将字母进行标记,表示已经用过
}
else{ //如果这个单词已经在map中存过了,那么就看pattern中对应的字母是否和map映射的相同
if(m[word] != pattern[index]){ //如果不相同的话,则说明不匹配
return false;
}
}
word = "";
index++;
}
else{
word+=str[i];
}
}
if(index != pattern.length()){ //如果下标和pattern的长度不对应,则说明pattern的字母数和str的单词数不对应,即不匹配
return false;
}
return true;
}
};