一 唠唠嗑
今天有点晚,直接上题了,一毛钱的都不跟你们唠
二 上题!
Q:已知字符串pattern与字符串str,确认str是否与pattern匹配。str与pattern匹配代表字符串str中的单词与pattern中的字符一一对应。(其中pattern中只包含小写字符,str中
的单词只包含小写字符,使用空格分隔。)
例如:
pattern = “abba”, str = “dog cat cat dog” 匹配.
pattern = “abba”, str = “dog cat cat fish” 不匹配.
pattern = "aaaa", str = "dog cat cat dog"不匹配.
pattern = "abba", str = "dog dog dog dog"不匹配.
三 想想?
冷静分析:
1.当切分出一个单词时,若该单词已出现过,那么这个单词对应的pattern字符,必须也是之前出现时对应的pattern字符
2.当切分出一个单词时,若该单词没有出现过,则与之对应的pattern字符也不能出现过
3.单词的个数必须与pattern中字符的数量相同
那么问题来了,我们怎么将一个单词和一个字符绑定在一起呢?
这里引入新的概念,哈希map
如果用一句话解释,它就是个key-value的数据结构,保存的是key到value的映射
在c++标准STL中也支持了这种数据结构,只需#include<map>即可使用
举个栗子,大家就对哈希map的使用了解了
//
// Created by renyi on 2019-06-13.
//
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main(){
map<string, int> hash_map;//初始化一个字符串string到整型int的映射,即哈希map
string string1 = "abc";
string string2 = "aaa";
string string3 = "wwwwwww";
//建立了三个字符串到整型的映射
hash_map[string1] = 1;
hash_map[string2] = 2;
hash_map[string3] = 3;
if (hash_map.find(string1) != hash_map.end()){//如果在哈希map中找到了string1
printf("%s is in hash map, and it's value is:%d\n", string1.c_str(), hash_map[string1]);
}
map<string, int> ::iterator it;//初始化一个迭代器指针it,指向一个从string到int的映射
for (it = hash_map.begin(); it != hash_map.end(); it++) {//it指向了hash_map
printf("hash_map[%s] = %d\n", it->first.c_str(), it->second);//it->first就是当前的映射的第一个元素,就是字符串string,it->second同理
}
return 0;
}
运行结果
怎么样,是不是对hash map的用法瞬间通透了
在这还要十分建议大家底下自行了解一下hash map原理,十分有用,你懂得
好了,知道怎么用hash map之后,我们可以这样处理逻辑:
1.建立单词到单个字符的哈希映射,使用数组used[128]来标志,当前的单个字符是否已被使用
2.遍历单词字符串str,按照空格切分单词,同时移动pattern下标,判断:
如果该单词从未出现在哈希表中:
如果当前的pattern单个字符已被使用,返回false,不匹配;
如果当前pattern字符没被使用,那么:
建立该单词到单个字符的映射,同时标记单个字符已被使用;
如果该单词出现在了哈希表中:
检查该单词应该匹配的字符,是否与当前pattern字符相同,如果相同,则匹配,如果不相同,则返回false
如果单词个数与pattern字符数量不一致:
返回false,不匹配
四 完整代码及十分详细的注释
//
// Created by renyi on 2019-06-13.
//
#include <iostream>
#include <string>
#include <map>
using namespace std;
bool wordPattern(string pattern, string str){
map<string, char> word_map;//初始化单词到pattern字符的映射,即哈希map
char used[128] = {0};//初始化一个字符数组,即字符哈希,保存已被映射过的pattern字符
string word;//临时保存拆分出来的单词
int position = 0;//当前指向的pattern字符
str.push_back(' ');//保存单词的str,尾部push一个空格,使遇到空格,切分最后一个单词
for (int i = 0; i < str.length(); i++) {
if (str[i] == ' '){//遇到了空格,即切分出了一个单词
if (position == pattern.length()){//若此时position位置为pattern长度(注意pattern下标从0开始),即超出了pattern长度,pattern已无字符对应
return false;
}
if (word_map.find(word) == word_map.end()){//在哈希map中找不到word时,find函数返回的迭代器指针,与end函数返回的迭代器指针相同,即,当该单词从未出现在哈希map中
if (used[pattern[position]]){//若当前pattern字符已使用,返回错误.比如“dog dog fish”和“aaa”
return false;
}
word_map[word] = pattern[position];//建立单词到单个字符的映射
used[pattern[position]] = 1;//把当前单个字符的used数组
}
else {//若find函数返回的迭代器指针不等于end函数返回的迭代器指针,即哈希map中已找到了该单词,即当前单词已与单个字符建立映射
if (word_map[word] != pattern[position]){
return false;//如果当前已经与单词建立映射的单个字符,并不等于pattern中的字符,即比如“dog cat cat”与“abc”
}
}
word = "";//将临时变量pattern置空
position++;//pattern的下标,即position向后移
} else{//没遇到空格,就把当前字符累加到word中,遇到空格时,word就是一个完整的单词了
word += str[i];
}
}
if (position != pattern.length()){
return false;//当单词str遍历结束,position还没到pattern尾,说明pattern更长,无法满足匹配
}
return true;//前面的false都没走到,即正常匹配,返回true
}
int main(){
string pattern = "abba";
string str = "dog cat cat fish";
if (wordPattern(pattern, str)){
printf("字符串:%s,与pattern:%s 正常匹配\n", str.c_str(), pattern.c_str());
} else{
printf("字符串:%s,与pattern:%s 不匹配\n", str.c_str(), pattern.c_str());
}
return 0;
}
测试一下:
不匹配的
匹配的
五 总结
还是一定要了解hash map原理
好了,有点晚了,实现一下,然后大家晚安