[890. find and replace mode]

source ： Power button （LeetCode）

describe ：

You have a list of words words And a pattern pattern, Do you want to know words Which words in match the pattern .

If there is an arrangement of letters p , Make every letter in the pattern x Replace with p(x) after , We get the words we need , So the words match the patterns .

（ Think about it , The arrangement of letters is from letter to letter ： Each letter maps to another letter , No two letters map to the same letter .）

return words List of words matching the given pattern in .

You can return the answers in any order .

Example ：

 Input ：words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
 Output ：["mee","aqq"]
 explain ：
"mee"  Match pattern , Because there are permutations  {
    a -> m, b -> e, ...}.
"ccc"  Does not match pattern , because  {
    a -> c, b -> c, ...}  It's not a permutation .
 because  a  and  b  Map to the same letter .
 

Tips ：

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

Method ： Constructive bijection

We can judge one by one words Every word in word Whether or not pattern matching .

According to the meaning , We need to construct a bijection from letter to letter , namely word Each letter of needs to be mapped to pattern Corresponding letter of , also pattern Each letter of also needs to be mapped to word Corresponding letter of .

We can write a function match(word,pattern), Only when the word The same letters in the map to pattern Returns... When the same letter in true. We can traverse these two strings while , Use a hash table to record word Every letter of x Need to map to pattern Which letter of , If x Already mapped , You need to check whether the corresponding letters are the same .

If match(word,pattern) and match(pattern,word) Are all true, said word And pattern matching .

Code ：

class Solution {
    
    bool match(string &word, string &pattern) {
    
        unordered_map<char, char> mp;
        for (int i = 0; i < word.length(); ++i) {
    
            char x = word[i], y = pattern[i];
            if (!mp.count(x)) {
    
                mp[x] = y;
            } else if (mp[x] != y) {
     // word  The same letter in must be mapped to  pattern  On the same letter in 
                return false;
            }
        }
        return true;
    }

public:
    vector<string> findAndReplacePattern(vector<string> &words, string &pattern) {
    
        vector<string> ans;
        for (auto &word: words) {
    
            if (match(word, pattern) && match(pattern, word)) {
    
                ans.emplace_back(word);
            }
        }
        return ans;
    }
};

Execution time ：4 ms, In all C++ Defeated in submission 66.05% Users of
Memory consumption ：8.2 MB, In all C++ Defeated in submission 59.88% Users of
Complexity analysis
Time complexity ： O(nm), among n It's an array words The length of ,m yes pattern The length of . For each word need O(m) Time to check if it is consistent with pattern matching .
Spatial complexity ： O(m). Hash table needs O(m) Space .
author：LeetCode-Solution