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.

Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

例子

pattern = "abba", str = "dog cat cat dog" should return true.
pattern = "abba", str = "dog cat cat fish" should return false.
pattern = "aaaa", str = "dog cat cat dog" should return false.
pattern = "abba", str = "dog dog dog dog" should return false.

分析

参考205. Isomorphic Strings。Isomorphic Strings要求两个字符串字符与字符的双射，本题则要求Pattern的字符与str的子字符串之间的双射。

• 方法一：用string::find方法切割str字符串
• 方法二：用istringstream流处理str字符串

要点

• 理解双射的概念；
• 如何切割字符串（string::find or istringstream）.

时间复杂度

O(n)

空间复杂度

O(1)

代码

方法一

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        str += ' '; // add a dummy space to find the last substring
        unordered_map<char, int> pmap;
        unordered_map<string, int> smap;
        size_t pos = 0;
        for (int i = 0; i < pattern.size(); i++) {
            size_t nextPos = str.find(' ', pos);
            if (nextPos == string::npos) return false;
            
            string substr(str.substr(pos, nextPos - pos));
            if (pmap[pattern[i]] != smap[substr]) return false;
            
            pmap[pattern[i]] = i + 1;
            smap[substr] = i + 1;
            pos = nextPos + 1;
        }
        return pos == str.size();
    }
};

方法二

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        unordered_map<char, int> pumap;
        unordered_map<string, int> sumap;
        istringstream iss(str);
        int i = 0, n = pattern.size();
        for (string substr; iss >> substr; i++) {
            if (i == n || pumap[pattern[i]] != sumap[substr]) 
                return false;
            pumap[pattern[i]] = sumap[substr] = i + 1;
        }
        return i == n;
    }
};