Q:
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
.
Example 1:
Input: pattern ="abba"
, str ="dog cat cat dog"
Output: true
Example 2:
Input:pattern ="abba"
, str ="dog cat cat fish"
Output: false
Example 3:
Input: pattern ="aaaa"
, str ="dog cat cat dog"
Output: false
Example 4:
Input: pattern ="abba"
, str ="dog dog dog dog"
Output: false
Notes:
You may assume pattern
contains only lowercase letters, and str
contains lowercase letters that may be separated by a single space.
Two hashMap
学到的: split string into words
string str
vector<string> vec; istringstream iss(str); for(string s; iss >> s; ) vec.push_back(s);
class Solution { public: bool wordPattern(string pattern, string str) { vector<string> vec; istringstream iss(str); for(string s; iss >> s; ) vec.push_back(s); unordered_map<char,string> map1; unordered_map<string,char> map2; if(pattern.length() != vec.size()) return false; for(int i = 0;i<pattern.length();++i){ char ch = pattern[i]; string word = vec[i]; if(map1.find(ch) == map1.end()){ map1[ch] = word; }else{ if(map1[ch] != word) return false; } if(map2.find(word) == map2.end()){ map2[word] = ch; }else{ if(map2[word] != ch) return false; } } return true; } };
----------
No comments:
Post a Comment