290. Word Pattern
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.
给定一个pattern字符串和一个实例字符串str，问这个str和pattern是否是一个双射（bijection）。双射这个词很重要，这表明str要和pattern一致，pattern也要和str一致。比如题目中第四个例子，str其实是符合pattern的，因为pattern说首尾和中间两个单词需要分别相等，但是a和b一定相等吗？我们从pattern对应到str就不行了，因为str四个单词都相等，但pattern的a和b不相等。 所以我们首先把str切分成单词数组，然后构建两个unordered_map分别对应pattern到str的映射和str到pattern的映射。只有当两个映射都正确才正确。 完整代码如下：
class Solution {
public:
bool wordPattern(string pattern, string str)
{
vector<string> segs;
int s = 0;
for (int t = 1; t <= str.size(); ++t) {
if (t == str.size() || str[t] == ‘ ‘) {
segs.push_back(str.substr(s, t – s));
s = t + 1;
}
}
if (pattern.size() != segs.size())
return false;
unordered_map<char, string> bijection1;
unordered_map<string, char> bijection2;
for (int i = 0; i < pattern.size(); ++i) {
if (bijection1.find(pattern[i]) == bijection1.end()) {
bijection1[pattern[i]] = segs[i];
}
else {
if (bijection1[pattern[i]] != segs[i])
return false;
}
if (bijection2.find(segs[i]) == bijection2.end()) {
bijection2[segs[i]] = pattern[i];
}
else {
if (bijection2[segs[i]] != pattern[i])
return false;
}
}
return true;
}
};
本代码提交AC，用时0MS。
二刷。很简单：
class Solution {
public:
bool wordPattern(string pattern, string str) {
vector<string> words;
int i = 0, j = 0, n = str.size();
while (i < n) {
j = i + 1;
while (j < n&&str[j] != ' ')++j;
string word = str.substr(i, j - i);
words.push_back(word);
i = j + 1;
}
if (pattern.size() != words.size())return false;
int m = pattern.size();
unordered_map<char, string> hash1;
unordered_map<string, char> hash2;
for (int i = 0; i < m; ++i) {
if (hash1.find(pattern[i]) == hash1.end()) {
hash1[pattern[i]] = words[i];
}
if (hash2.find(words[i]) == hash2.end()) {
hash2[words[i]] = pattern[i];
}
if (hash1[pattern[i]] != words[i] || hash2[words[i]] != pattern[i])return false;
}
return true;
}
};
本代码提交AC，用时0MS。
观察的时候需要分组观察，比如[0,1]的结果为0,1，[2,3]的结果为1,2，也就是在[0,1]的结果上加了1；[4,7]的结果为1,2,2,3，也就是在[0,3]的结果上加了1；[8,15]的结果为1,2,2,3,2,3,3,4，也就是在[0,7]的结果上加了1。
所以重复的周期是以2的幂递增的，初始的时候，我们可以在ans数组中只存[0,1]的结果，然后每次添加2的幂个结果进ans，直到ans的大小大于num为止。
完整代码如下：
[cpp]
class Solution {
public:
vector<int> countBits(int num) {
vector<int> ans = { 0,1 };
while (ans.size() <= num) {
int old_size = ans.size();
for (int i = 0; i < old_size; ++i) {
ans.push_back(ans[i] + 1);
}
}
return vector<int>(ans.begin(), ans.begin() + num + 1);
}
};
[/cpp]
本代码提交AC，用时73MS。
]]>