Problem description:

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

Solution:

build a function that can normalize the string into a same form.
if a word appears the first time, then we mark it as the size of string in the map.
Since all same pattern would have new letter in the same position, after normalize, they’ll become same word.

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 p) {
        //normalize words into same patter
        //ex: ppood -> aabbc, qqwwf -> aabbc
        vector<string> res;
        for(auto w: words){
            if(normalize(w) == normalize(p)) res.push_back(w);
        }
        return res;
    }
    
    string normalize(string w){
        unordered_map<char, int> map;
        for(auto c: w) if(!map.count(c)) map[c]= map.size();
        for(int i= 0; i< w.length(); i++) 
            w[i]= 'a'+ map[w[i]];
        return w;
    }
    
};

time complexity: $O(n*m)$
space complexity: $O(1)$
reference:
https://goo.gl/M1DEku