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.

这道题需要我们对给定的字符串进行判断，判断其是否符合一个模式(其实小学语文中就有这个概念)，那么主要的思路还是使用一个哈希表建立起pattern字符串和需要判断的字符串的映射即可。

建立之后,我们首先查找pattern字符串的元素是否存在于哈希表中，如果存在，则判断其映射的字符串是否和当前字符串相等，若不相等，则返回false;

如果第一步判断出不存在，则需要遍历整个哈希表，判断其映射的字符串是否存在于哈希表中，如果存在，则返回false，否则，才可以将这个pattern字符串及其映射的字符串加入到哈希表中去。

最后返回true的条件是i==pattern.size(),因为只有完成整个循环后才能说明是完全匹配的，代码如下:

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();
    }
};