leetcode/290.word-pattern.cpp at main · ming197/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/*
 * @lc app=leetcode id=290 lang=cpp
 *
 * [290] Word Pattern
 */

// @lc code=start
#include "bits/stdc++.h"
using namespace std;
class Solution {
public:
    bool wordPattern(string pattern, string s) {
        // use bi-directional map to check the bijection of pattern and s
        unordered_map<char, string> pattern2s;
        unordered_map<string, char> s2pattern;
        // two pointers for string division
        int l = 0, r = 0;
        int n = s.size();
        int k = 0;
        int m = pattern.size();
        while (l < n && k < m)
        {
            while (r < n && s[r] != ' ')
            {
                ++r;
            }
            string word = s.substr(l, r - l);
            if (pattern2s.find(pattern[k]) == pattern2s.end() && s2pattern.find(word) == s2pattern.end())
            {
                pattern2s[pattern[k]] = word;
                s2pattern[word] = pattern[k];
            }
            else if (pattern2s[pattern[k]] != word || s2pattern[word] != pattern[k])
            {
                return false;
            }
            // update l and r
            l = r + 1;
            r = l;
            ++k;
        }
        return k == m && l == n + 1;
    }
};

int main()
{
    Solution sol;
    assert(sol.wordPattern("abba", "dog cat cat dog") == true);
    assert(sol.wordPattern("abba", "dog cat cat fish") == false);
    assert(sol.wordPattern("aaaa", "dog cat cat dog") == false);
    assert(sol.wordPattern("abba", "dog dog dog dog") == false);
    return 0;
}
// @lc code=end