290. 单词规律
给定一种规律 pattern 和一个字符串 s ,判断 s 是否遵循相同的规律。
这里的 遵循 指完全匹配,例如, pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。
class Solution {
public:
bool wordPattern(string pattern, string s) {
unordered_map<char,string> countmap1;
unordered_map<string,char> countmap2;
string tmp="";
int j=-1;
int count=0;
char tmpchar;
for(int i=0;i<s.size();i=j+1){
j=i;
while(s[j]!=' ' && j<s.size()){
j++;
}
tmp=s.substr(i,j-i);
tmpchar=pattern[count++];
if(countmap1.find(tmpchar)==countmap1.end() && countmap2.find(tmp)==countmap2.end()){
//双向不匹配,建立双向匹配
countmap1[tmpchar]=tmp;
countmap2[tmp]=tmpchar;
}else if(countmap1[tmpchar]!=tmp || countmap2[tmp]!=tmpchar){
return false;
}
}
if(count!=pattern.size()){
return false;
}
return true;
}
};
哈希表(Hash Table)通常是一种单向映射数据结构,其中每个键(key)都映射到一个值(value)。这意味着你可以使用键来获取相应的值,但不能直接使用值来获取键。然而,有时候也需要实现双向映射,即能够通过键找到值,同时也能通过值找到键。在这种情况下,可以考虑使用两个哈希表来实现这种双向映射。
例如,你可以创建两个哈希表,一个用于键到值的映射,另一个用于值到键的映射。这样,在插入新的键值对时,同时在这两个哈希表中进行插入操作。这种方式可以在常量时间内实现双向查找。但需要注意的是,确保维护这两个哈希表的一致性,即在插入、更新或删除操作时,同时更新两个哈希表。
然而,这种方法也存在一些问题,特别是在内存使用和维护成本方面。另一种选择是使用一些已有的双向映射数据结构,如有序映射(Ordered Map)或双向链表(Doubly Linked List)。这些数据结构在一些编程语言的标准库中已经提供,可以直接使用,而不需要手动实现哈希表的双向映射。
总之,哈希表的双向映射可以通过维护两个哈希表或使用现有的双向映射数据结构来实现。选择哪种方法取决于具体的情况和需求。