Word Pattern

Posted on Edited on In Views:

290.Word Pattern

Given a pattern and a string s, find if s 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 s.

Example 1:

1
2
Input: pattern = "abba", s = "dog cat cat dog"
Output: true

Example 2:

1
2
Input: pattern = "abba", s = "dog cat cat fish"
Output: false

Example 3:

1
2
Input: pattern = "aaaa", s = "dog cat cat dog"
Output: false

哈希表：

时间复杂度：O(n+m)，n为pattern长度，m为s长度

空间复杂度：O(n+m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool wordPattern(string pattern, string s) {
        int s_size = s.size();
        unordered_map<char, string>pattern_s;
        unordered_map<string, char>s_pattern;
        int i = 0;
        for (char ch : pattern) {
            string str;
            for (; i < s_size;i++) {
                if (s[i] == ' ')break;
                str += s[i];
            }
            i++;
            if(pattern_s.count(ch)&&pattern_s[ch]!=str||
               (s_pattern.count(str))&&s_pattern[str]!=ch)return false;
            pattern_s[ch] = str;
            s_pattern[str] = ch;
        }
        return i == s_size+1;
    }
};