290. Word Pattern

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Examples:

pattern = “abba”, str = “dog cat cat dog” should return true.

pattern = “abba”, str = “dog cat cat fish” should return false.

pattern = “aaaa”, str = “dog cat cat dog” should return false.

pattern = “abba”, str = “dog dog dog dog” should return false.

Notes:

You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

class Solution {
public:
bool wordPattern(string pattern, string str) {
unordered_map<char,string> hash;
istringstream in(str);/*构造字符串流时，空格会成为其内部分界，这也是拆分含有空格的字符串的方法之一*/
int i=0;
for(string word;in>>word;i++){
if(hash.find(pattern[i])!=hash.end()){
if(hash[pattern[i]]!=word)
return false;
}
else{
for(unordered_map<char,string>::iterator it=hash.begin();it!=hash.end();it++){
if(it->second==word)
return false;
}
hash[pattern[i]]=word;
}
}
return i==pattern.size();
}
};


学籍管理系统文档

北邮教务系统评教脚本

Published on September 17, 2017

72.Edit distance

Published on September 17, 2017