leetcode 291. Word Pattern II和290. Word Pattern

目录

291. Word Pattern II

290. Word Pattern

291. Word Pattern II

回溯法+哈希表

class Solution {
    unordered_map<char,string> hashmap;
    unordered_set<string> wordset;
public:
    bool wordPatternMatch(string pattern, string s) {
        return backtrack(pattern,0,s,0);
    }

    bool backtrack(const string& pattern,int pi,const string&s,int si){
        if(pi == pattern.size())
            return si == s.size();
        char c = pattern[pi];
        if(hashmap.contains(c)){
            string &word = hashmap[c];
            if((si+word.size() > s.size()) || (s.substr(si,word.size()) != word))
                return false;
            return backtrack(pattern,pi+1,s,si+word.size());
        }
        for(int k = si;k < s.size();k++){
            string newword = s.substr(si,k-si+1);
            if(wordset.contains(newword))
                continue;
            hashmap[c] = newword;
            wordset.insert(newword);
            if(backtrack(pattern,pi+1,s,k+1))
                return true;
            hashmap.erase(c);
            wordset.erase(newword);
        }
        return false;
    }
};

290. Word Pattern

哈希

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        vector<string> strvec;
        int slen = s.size();
        int start = 0;
        int len = 0;
        for(int i = 0;i <slen;i++){
            if(s[i] != ' '){
                len++;
            }
            else{
                strvec.push_back(s.substr(start,len));
                start=i+1;
                len = 0;
            }
        }
        strvec.push_back(s.substr(start,len));

        int pattern_len = pattern.size();
        if(pattern_len != strvec.size())
            return false;
        unordered_map<char,string> pattern2str;
        unordered_map<string,char> str2pattern;
        for(int i = 0; i<pattern_len;i++){
            if((pattern2str.contains(pattern[i])&&pattern2str[pattern[i]]!=strvec[i]) ||
               (str2pattern.contains(strvec[i])&&str2pattern[strvec[i]]!=pattern[i]) )
                return false;
            pattern2str[pattern[i]] = strvec[i];
            str2pattern[strvec[i]] = pattern[i];
        }
        return true;
    }
};

用stringstream分割字符串

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        vector<string> strvec;
        string word;
        stringstream ss(s);
        while(ss>>word)
            strvec.emplace_back(word);

        int pattern_len = pattern.size();
        if(pattern_len != strvec.size())
            return false;
        unordered_map<char,string> pattern2str;
        unordered_map<string,char> str2pattern;
        for(int i = 0; i<pattern_len;i++){
            if((pattern2str.contains(pattern[i])&&pattern2str[pattern[i]]!=strvec[i]) ||
               (str2pattern.contains(strvec[i])&&str2pattern[strvec[i]]!=pattern[i]) )
                return false;
            pattern2str[pattern[i]] = strvec[i];
            str2pattern[strvec[i]] = pattern[i];
        }
        return true;
    }
};