力扣-290.单词规律

Idea

1. 先建立一个hashmap，记录s串中的每个单词以及对应的下标
2. 再建立一个hashmap，记录pattern串中相同字母以及对应的下标
3. 遍历pattern串时，遇到不同字母存到pat表中，同时将下标对应的s中的单词存入到查重test集中，因为如果输入样例为"abba",“dog dog dog dog”，无法得出正确答案
4. 最后通过比较pattern中有相同字母的位置对应s中出现相同的word即可，否则为false

AC Code

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        unordered_map<char,int> pat;
        unordered_map<int,string> word;
        int n = s.size();
        int index = 0;
        for(int i = 0; i < n; i++) {
            string tmp = "";
            while(s[i] != ' ' && i < n){
                tmp += s[i];
                i++;
            }
            word[index++] = tmp;
        }
        if(word.size() != pattern.size()) return false;
        unordered_set<string> test;
        for(int i = 0; i < pattern.size(); i++) {
            if(pat.find(pattern[i]) == pat.end()){
                pat[pattern[i]] = i;
                if(test.find(word[i]) != test.end()){
                    return false;
                }
                test.insert(word[i]);
            }
            else {
                int con1 = pat[pattern[i]];
                int con2 = i;
                if(word[con1] != word[con2]) return false;
                if(pattern[con1] != pattern[con2]) return false;
            }
        }
        return true;
    }
};
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