LEETCODE ALGORITHM:890. Find and Replace Pattern

发表于 更新于 分类于 Waline： 阅读次数：

题目

You have a list of words and a pattern, and you want to know which words in words matches the pattern.

A word matches the pattern if there exists a permutation of letters p so that after replacing every letter x in the pattern with p(x), we get the desired word.

(Recall that a permutation of letters is a bijection from letters to letters: every letter maps to another letter, and no two letters map to the same letter.)

Return a list of the words in words that match the given pattern.

You may return the answer in any order.

Example 1:

1
2
3
4
5
Input: words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
Output: ["mee","aqq"]
Explanation: "mee" matches the pattern because there is a permutation {a -> m, b -> e, ...}. 
"ccc" does not match the pattern because {a -> c, b -> c, ...} is not a permutation,
since a and b map to the same letter.

Note:

  • 1 <= words.length <= 50
  • 1 <= pattern.length = words[i].length <= 20

题解

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
//相当于单映射法，只保存pattern到words的字母映射，在保存已经words已经用过的字母，不允许重复映射即可
class Solution {
public:
    vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
        vector<string> ans;
        for(int i=0;i<words.size();i++)
        {
            unordered_map<char,char> tmp;
            unordered_set<char> t2;
            int flag=1;
            for(int j=0;j<pattern.length();j++)
            {
                if(tmp.find(pattern[j])==tmp.end()&&t2.find(words[i][j])==t2.end())
                {
                    tmp[pattern[j]]=words[i][j];
                    t2.emplace(words[i][j]);
                } 
                else if(tmp[pattern[j]]!=words[i][j])
                {
                    flag=0;
                    break;
                } 
            }
            if(flag) ans.push_back(words[i]);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//评论区看到的很精妙的写法
class Solution {
public:
    vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
        vector<string> res;
        for(int i=0;i<words.size();i++){
           if(check(words[i],pattern)) res.push_back(words[i]); 
        }
        return res;
    }
    bool check(string word,string pattern)
    {
     if(word.length()!=pattern.length()) return false;
     for(int i=0;i<pattern.length();i++)
     {
         if(word.find(word[i])!=pattern.find(pattern[i])) return false;
         //find会返回第一个找到的下标，如果不相等表示对应关系变了
     }
     return true;
    }
};