目錄

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