# LeetCode290. Word Pattern（模拟）

## LeetCode290. Word Pattern（模拟）

• Easy
• Accepted：128,851
• Submissions：374,057

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 separated by a single space.

### 链接

https://leetcode.com/problems/word-pattern/

### 题解

unordered_map匹配一下就好了，将字符串和对应的模式字符建立映射关系，然后进行判断即可。注意一下要按空格对字符串str进行分割，用string的substr完成。

### 代码

• Runtime: 4 ms, faster than 100.00% of C++ online submissions for Word Pattern.
• Memory Usage: 8.7 MB, less than 100.00% of C++ online submissions for Word Pattern.
class Solution {
public:
bool wordPattern(string pattern, string str) {
vector <string> vt;
stringSpilt(str, vt);
int n = pattern.length(), m = vt.size();
unordered_map<string, char> umap;
bool vis[256]; // 对模式的字符进行标记
memset(vis, 0, sizeof vis);
int i;
for (i = 0; i < m; ++i)
{

if (!umap.count(vt[i]) && !vis[pattern[i]]) // 字符串不在map中且模式字符没用过就加入
{
umap.insert(make_pair(vt[i], pattern[i]));
vis[pattern[i]] = true;
}
if (umap.count(vt[i]) > 0 && umap[vt[i]] != pattern[i]) // 在map中则模式字符要相同
break;
if (!umap.count(vt[i]) && vis[pattern[i]]) // 不在map中则模式字符要没用过
break;
}
return  i == m && i == n;
}

void stringSpilt(string s, vector<string> &vt) // 对字符串进行分割
{
int n = s.length();
vector <int> pos;
pos.push_back(0);
for (int i = 0; i < n; ++i)
{
if (s[i] == ' ')
pos.push_back(i + 1);
}
pos.push_back(n + 1);
int cnt = pos.size();
for (int i = 0; i < cnt - 1; ++i)
{
// cout << s.substr(pos[i], pos[i+1] - pos[i] - 1);
// cout << " " << pos[i] << " " << pos[i+1] - pos[i] - 1 << endl;
vt.push_back(s.substr(pos[i], pos[i+1] - pos[i] - 1));
}
}
};

### 补充

bool wordPattern(string pattern, string str) {
istringstream strcin(str);
string s;
vector<string> vs;
while(strcin >> s) vs.push_back(s);
if (pattern.size() != vs.size()) return false;
map<string, char> s2c;
map<char, string> c2s;
for (int i = 0; i < vs.size(); ++i) {
if (s2c[vs[i]] == 0 && c2s[pattern[i]] == "") {
s2c[vs[i]] = pattern[i];
c2s[pattern[i]] = vs[i];
continue;
}
if (s2c[vs[i]] != pattern[i]) return false;
}
return true;
}

The end.
2019年2月15日 星期五