class Solution {
public:
    bool wordPattern(string pattern, string str) {
        unordered_map<char, int> char2pos;
        unordered_map<string, int> str2pos;
        istringstream in(str);
        int i = 0;
        for (string word; in >> word; i++) {
            //pattern or word have existed previously, check whether equal
            if (char2pos.find(pattern[i]) != char2pos.end() || str2pos.find(word) != str2pos.end()) {
                if (char2pos[pattern[i]] != str2pos[word]) return false;
            } 
            //pattern & word add to the map
            else {
                char2pos[pattern[i]] = str2pos[word] = i + 1;
            }
        }
        return i == pattern.size();
    }
};

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        unordered_map<char, string> char2str;
        unordered_set<string> dict;
        istringstream in(str);
        int i = 0;
        for (string word; in >> word; i++) {
            if (char2str.find(pattern[i]) != char2str.end()) {
                if (char2str[pattern[i]] != word) return false;
            } else {
                if (dict.find(word) != dict.end()) return false;
                char2str[pattern[i]] = word;
            }
            dict.insert(word);
        }
        return i == pattern.size();
    }
};

class Solution {
    unordered_set<string> str;
    unordered_map<char, string> pat2str;
public:
    bool wordPatternMatch(string pattern, string str) {
        return dfs(str, 0, pattern, 0);
    }
private:
    bool dfs(string& str, int pos_str, string& pat, int pos_pat) {
        if (pos_str == str.size() && pos_pat == pat.size()) return true;
        if (pos_str == str.size() || pos_pat == pat.size()) return false;
        char ch = pattern[p];
        for (int i = pos_str; i < str.size(); i++) {
            string cur = str.substr(pos_str, i - pos_str + 1);
            //char ch and the cur string both exist previously
            if (pat2str.count(ch) && pat2str[ch] == cur) {
                if (dfs(str, i + 1, pat, pos_pat + 1)) return true;
            } 
            //char ch not exist before, check whether the cur exist previously
            else if (!pat2str.count(ch)) {
                //current string exists previosly, so continue !
                if (str.count(cur)) continue;
                //not exist before, just add it 
                pat2str[ch] = cur;
                str.insert(cur);
                if (dfs(str, i + 1, pat, pos_pat + 1)) return true;
                pat2str.erase(ch);
                str.erase(cur);
            }
        }
        return false;
    }
};