leetcode 290. Word Pattern 、lintcode 829. Word Pattern II

290. Word Pattern 

istringstream 是将字符串变成字符串迭代器一样，将字符串流在依次拿出，比较好的是，它不会将空格作为流，这样就实现了字符串的空格切割。

C++引入了ostringstream、istringstream、stringstream这三个类，要使用他们创建对象就必须包含sstream.h头文件。

istringstream类用于执行C++风格的串流的输入操作。 
ostringstream类用于执行C风格的串流的输出操作。 
strstream类同时可以支持C风格的串流的输入输出操作。

1.本题中str是带空格的字符串，需要将每个词根据提取出来，就使用istringstream。

2.本题要求的是pattern中的字符和str中的单词是一一对应的，所以不仅要判断当前pattern字符与存储在hash中的的映射是否相同，还需要判断hash中映射的string是否与当前string相同。

3.可能存在pattern和str个数不一样的情况，所以最后使用i == n来判断。

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        unordered_map<char,string> m;
        istringstream in(str);
        int i = 0,n = pattern.size();
        for(string tmp;in >> tmp;i++){
            if(m.find(pattern[i]) == m.end()){
                for(auto it = m.begin();it != m.end();it++){
                    if(it->second == tmp)
                        return false;
                }
                m[pattern[i]] = tmp;
            }
            else{
                if(m[pattern[i]] != tmp)
                    return false;
            }
        }
        return i == n;
    }
};

这种情况就是两者个数不相同。

Input:
"jquery"
"jquery"
Output:
true
Expected:
false

829. Word Pattern II

https://www.cnblogs.com/grandyang/p/5325761.html

不知道哪个单词对应哪个词，就用递归去搜索每种可能性

class Solution {
public:
    /**
     * @param pattern: a string,denote pattern string
     * @param str: a string, denote matching string
     * @return: a boolean
     */
    bool wordPatternMatch(string &pattern, string &str) {
        // write your code here
        unordered_map<char,string> m;
        int index1 = 0,index2 = 0;
        return wordPatternMatch(pattern,index1,str,index2,m);
    }
    bool wordPatternMatch(string &pattern,int index1,string &str,int index2,unordered_map<char,string> &m){
        if(index1 == pattern.size() && index2 == str.size())
            return true;
        if(index1 == pattern.size() || index2 == str.size())
            return false;
        char word = pattern[index1];
        for(int i = index2;i < str.size();i++){
            string tmp = str.substr(index2,i - index2 + 1);
            if(m.count(word) && m[word] == tmp){
                if(wordPatternMatch(pattern,index1+1,str,i+1,m))
                    return true;
            }
            else if(!m.count(word)){
                bool flag = false;
                for(auto it : m){
                    if(it.second == tmp)
                        flag = true;
                }
                if(!flag){
                    m[word] = tmp;
                    if(wordPatternMatch(pattern,index1+1,str,i+1,m))
                        return true;
                    m.erase(word);
                }
            }
        }
    }
};

自己又写了一个版本：

其实主要是如果当前不满足true的条件，就继续遍历

if(m.find(word) != m.end()){
　　if(m[word] == tmp){
　　　　if(wordPatternMatch(pattern,str,index1+1,i+1,m))
　　　　　　return true;
　　}
}

如果word != tmp，不做任何处理直接继续遍历下一个位置就好了

if(flag)
　　continue;

如果在map中找到了tmp，也就不满足条件，这个时候也不做任何处理，直接继续遍历就好了

class Solution {
public:
    /**
     * @param pattern: a string,denote pattern string
     * @param str: a string, denote matching string
     * @return: a boolean
     */
    bool wordPatternMatch(string &pattern, string &str) {
        // write your code here
        unordered_map<char,string> m;
        int index1 = 0,index2 = 0;
        return wordPatternMatch(pattern,str,index1,index2,m);
    }
    bool wordPatternMatch(string pattern,string str,int index1,int index2,unordered_map<char,string> m){
        if(index1 == pattern.size() && index2 == str.size())
            return true;
        else if(index1 == pattern.size() || index2 == str.size())
            return false;
        char word = pattern[index1];
        for(int i = index2;i < str.size();i++){
            string tmp = str.substr(index2,i - index2 + 1);
            if(m.find(word) != m.end()){
                if(m[word] == tmp){
                    if(wordPatternMatch(pattern,str,index1+1,i+1,m))
                        return true;
                }
            }
            else{
                bool flag = false;
                for(auto it = m.begin();it != m.end();it++){
                    if(it->second == tmp){
                        flag = true;
                        break;
                    }
                }
                if(flag)
                    continue;
                m[word] = tmp;
                if(wordPatternMatch(pattern,str,index1+1,i+1,m))
                    return true;
                m.erase(word);
            }
        }
    }
};