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。