Word Pattern

Problem: 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.

Solution:
class Solution {
public:
    bool wordPattern(string pattern, string str) {
        vector<string> splitString;
        if (str.size() != 0) {
            split(str, splitString);
        }
        if (pattern.size() != splitString.size()) {
            return false;
        }
        int size = pattern.size();
        map<char, string> map1;
        map<string, char> map2;
        for (int i = 0; i < size; i++) {
            if (map1.find(pattern[i]) != map1.end()) {
                if (map1[pattern[i]] != splitString[i]) {
                    return false;
                }
            } else {
                map1[pattern[i]] = splitString[i];
            }
         
            // Backword map check.
            if (map2.find(splitString[i]) != map2.end()) {
                if (map2[splitString[i]] != pattern[i]) {
                    return false;
                }
            } else {
                map2[splitString[i]] = pattern[i];
            }
        }
        return true;
    }
 
    void split(string str, vector<string>& splitString) {
        stringstream s(str);
        string token;
        while (getline(s, token, ' ')) {
            splitString.push_back(token);
        }
        return;
    }
};


============== Another =======
class Solution {
public:
    bool wordPattern(string pattern, string str) {
        map<char, string> mp1;
        map<string, char> mp2;
       
        vector<string> tmp = split(str, ' ');
        if (tmp.size() != pattern.size()) {
            return false;
        }
       
        for (int i = 0; i < pattern.size(); i++) {
            if (!mp1.count(pattern[i])) {
                mp1[pattern[i]] = tmp[i];
            } else {
                if (mp1[pattern[i]] != tmp[i]) {
                    return false;
                }
            }
            if (!mp2.count(tmp[i])) {
                mp2[tmp[i]] = pattern[i];
            } else {
                if (mp2[tmp[i]] != pattern[i]) {
                    return false;
                }
            }
        }
        return true;
    }
   
    vector<string> split(string str, char delim) {
        vector<string> ans;
        stringstream ss(str);
        string partial;
        while (getline(ss, partial, delim)) {
            ans.push_back(partial);
        }
        return ans;
    }
};

========= Split ======
bool wordPattern(string pattern, string str) { stringstream raw(str); vector<string> strs; string line; while (raw >> line) strs.push_back(line); if (pattern.size() != strs.size()) return false; unordered_map<char, string> PS; unordered_map<string, char> SP; for (int i = 0; i < pattern.size(); i ++ ) { if (PS.count(pattern[i]) == 0) PS[pattern[i]] = strs[i]; if (SP.count(strs[i]) == 0) SP[strs[i]] = pattern[i]; if (PS[pattern[i]] != strs[i]) return false; if (SP[strs[i]] != pattern[i]) return false; } return true; }