Leetcode:890. Find and Replace Pattern

Posted on | Comments: | Views:
string map

890. Find and Replace Pattern

题目理解:

在给出的字符串中匹配 pattern, 其中 pattern 的映射满足以下要求:

  • 相同字母只能映射到相同的任意字母
  • 不同字母不能映射到相同的字母

思路:

  • 用map记录pattern的映射, 若无记录且可映射, 添加键值对; 有记录则需要检查映射是否匹配
  • 记录某个字母是否被映射过(这里用了map, 用数组亦可), 一个字母不能被多次映射
  • 遍历数组, 检查pattern映射

code:

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
class Solution {
public:
    map<char, char> CharMap;
    map<char, int> useMap;
    vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
        vector<string> ans;
        for (auto i:words) {
            CharMap.clear();
            useMap.clear();
            if (checkInPattern(i, pattern)) {
                ans.push_back(i);
            }
        }
        return ans;
    }
    bool checkInPattern(string str, string pattern) {
        if (str.size() != pattern.size()) {
            return false;
        }
        for (int i = 0; i < pattern.size(); i++) {
            if (CharMap.count(pattern[i]) == 0) {
                if (useMap.count(str[i]) == 0) {
                    CharMap[pattern[i]] = str[i];
                    useMap[str[i]] = 1;
                } else {
                    return false;
                }
            } else {
                if (CharMap[pattern[i]] != str[i]) {
                    return false;
                }
            }
        }
        return true;
    }
};