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:

1. pattern = "abba", str = "dog cat cat dog" should return true.
2. pattern = "abba", str = "dog cat cat fish" should return false.
3. pattern = "aaaa", str = "dog cat cat dog" should return false.
4. 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.

Credits:
Special thanks to @minglotus6 for adding this problem and creating all test cases.

Use a set and map, to check in both directions, pattern to string and string to pattern.

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        vector<string> strs = splitStr(str);
        if(pattern.size() != strs.size()) return false;
        unordered_map<string, char> map;
        unordered_set<char> set;
        for(int i = 0; i < pattern.size(); ++i){
            char p = pattern[i];
            string s = strs[i];
            if(map.find(s) == map.end()){
                if(set.count(p) > 0){
                    return false;
                }
                map[s] = p;
                set.insert(p);
            }
            else{
                if(map[s] != p){
                    return false;
                }
            }
        }
        return true;
    }
    vector<string> splitStr(string str){
        vector<string> ans;
        string tmp;
        str.push_back(' ');
        for(char c : str){
            if(c == ' ' && !tmp.empty()){
                ans.push_back(tmp);
                tmp.clear();
            }
            else if(c != ' '){
                tmp.push_back(c);
            }
        }
        return ans;
    }
};

Word Pattern II

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 substring in str.

Examples:

1. pattern = "abab", str = "redblueredblue" should return true.
2. pattern = "aaaa", str = "asdasdasdasd" should return true.
3. pattern = "aabb", str = "xyzabcxzyabc" should return false.

Notes:
You may assume both pattern and str contains only lowercase letters.

ALWAYS REMEMBER TO RETRIEVE SPOT BEFORE RETURN FROM CURRENT NODE IN DFS.

We need to maintain a set and map to guarantee bijection between pattern and string.

Calculate the maxLength of string of each pattern that they can match. It would prones the DFS search.

DFS search. O(s^p)

class Solution {
public:
    unordered_map<char, string> map;
    unordered_set<string> visitedStr;
    unordered_map<char, int> maxLength;
    bool wordPatternMatch(string pattern, string str) {
        map.clear();
        visitedStr.clear();
        maxLength.clear();
        unordered_set<char> set;
        for(char p : pattern){
            set.insert(p);
        }
        int lenp = pattern.size();
        int lens = str.size();
        if(lenp == 0 && lens == 0) return true;
        else if(lenp == 0 || lens == 0) return false;
        for(auto p: set){
            maxLength[p] = (lens - (lenp - set.count(p))) / set.count(p); 
        }
        return DFS(pattern, str);
    }
    bool DFS(string& pattern, string& str){
        int lenp = pattern.size();
        int lens = str.size();
        if(lenp == 0 && lens == 0) return true;
        if(lenp == 0 || lens == 0) return false;
        char p = pattern[0];
        pattern.erase(0, 1);
        for(int len = 1; len <= maxLength[p]; len++){
            string tmp = str.substr(0, len);
            str.erase(0, len);
            if(map.find(p) == map.end()){
                //new pattern
                if(visitedStr.count(tmp) == 0){
                    //new string
                    map[p] = tmp;
                    visitedStr.insert(tmp);//BUG HERE ADD IT
                    if (DFS(pattern, str)){
                        return true;
                    }
                    visitedStr.erase(tmp);//AND DELETE IT
                    map.erase(p);
                }
            }
            else{
                //visited pattern
                if(map[p] == tmp){
                    if(DFS(pattern, str)){
                        return true;
                    }
                }
            }
            str.insert(0, tmp);
        }
        pattern.insert(0, 1, p);//ADD IT
        return false;
    }
};