Word Pattern 1 & 2 & 3


  • 0
    F

    Word Pattern 1 --------- 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.

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

    Now let us look at the template solution for the Word Pattern 1&2

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

    *Word Pattern 2 ----------- 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:**

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

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.