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:
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

Difficulty: interview

Starter code:

class Solution:
    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
        

Solutions:
class Solution:
    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
        out = []
        for word in words:
            pat_dict = dict()
            used = set()
            if len(word) == len(pattern):
                can_be = True
                for i in range(len(word)):
                    if word[i] not in pat_dict:
                        if pattern[i] not in used:
                            pat_dict[word[i]] = pattern[i]
                            used.add(pattern[i])
                        else:
                            can_be = False
                            break
                    else:
                        if pat_dict[word[i]] != pattern[i]:
                            can_be = False
                            break
                if can_be == True:
                    out.append(word)
        return out

from collections import Counter
class Solution:
    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
        dp={}

        lstp=[]
        
        ans=[]
        for i,p in enumerate(pattern) :
            if p not in list(dp.keys()):
                dp[p]=i+1
            lstp.append(dp[p])
        #print(lstp)
        
        for word in words:
            dp={}
            lst=[]
            for j,w in enumerate(word):
                if w not in list(dp.keys()):
                    dp[w]=j+1
                lst.append(dp[w])
            #print(lst)
            if lstp==lst:
                ans.append(word)
        return ans
                
                
                
            


class Solution:
    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
        
        ans = []
        
        for i in words:
            temp = i
            
            if len(pattern) == len(temp):
                as1 = {}
                got = []
                found = 1
                for i1 in range(len(temp)):
                    if pattern[i1] not in as1:
                        if temp[i1] in got:
                            found = 0 
                            break
                        else:
                            as1[pattern[i1]] = temp[i1]
                            got.append(temp[i1])
                    else:
                        if temp[i1] != as1.get(pattern[i1]):
                            found = 0
                            break
                            
                if found == 1:
                    ans.append(temp)
                    
                    
        return ans
                        
                        
                        
                    
                    
                
            


class Solution:
    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
        output = []
        for word in words:
            fwd, reverse, valid = defaultdict(str), defaultdict(str), True
            for i in range(len(word)):
                if word[i] not in fwd and pattern[i] not in reverse:
                    fwd[word[i]] = pattern[i]
                    reverse[pattern[i]] = word[i]
                else:
                    valid = fwd[word[i]] == pattern[i] and reverse[pattern[i]] == word[i]
                if not valid: break
            if valid: 
                output.append(word)
        return output

class Solution:
    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
        output = []
        for word in words:
            fwd, reverse, valid = defaultdict(str), defaultdict(str), True
            for i in range(len(word)):
                if word[i] not in fwd and pattern[i] not in reverse:
                    fwd[word[i]] = pattern[i]
                    reverse[pattern[i]] = word[i]
                else:
                    valid = fwd[word[i]] == pattern[i] and reverse[pattern[i]] == word[i]
                    if not valid: break
            if valid: 
                output.append(word)
        return output

class Solution:
    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
        def encodeWord(word):
            d, nextChar, i, encoding = {}, iter([chr(ord('a') + i) for i in range(26)]), 0, []
            
            while i < len(word):
                c, count = word[i], 1
                while i + 1 < len(word) and word[i + 1] == c:
                    i, count = i + 1, count + 1
                if c not in d:
                    d[c] = next(nextChar)
                encoding.append(d[c] + str(count))
                i += 1
            return ''.join(encoding)
        
        p_enc = encodeWord(pattern)
        #print(p_enc)
        return [word for word in words if encodeWord(word) == p_enc]
            


class Solution:
    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
        plen = len(pattern)
        pat = [-1]*plen
        pat[0] = 0 
        for i in range(1,plen):
            for j in range(i):
                if pattern[j]==pattern[i]:
                    pat[i] = j
        res = []
        # print(pat)
        for word in words:
            wlen = len(word)
            flag = 0
            if wlen!=plen:
                continue
            for i in range(1,wlen):
                if pat[i]!=-1 and word[i]==word[pat[i]]:
                    continue
                elif pat[i]!=-1 and word[i]!=word[pat[i]]:
                    flag = 1
                    break
                else:
                    for j in range(i):
                        if word[j]==word[i]:
                            flag=1
                            break
            if flag == 0:
                res.append(word)
                    
        return res

class Solution:
    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
        #dict mapping
        #insert pattern into dict
        pattern_map = dict()
        for el in pattern:
            pattern_map[el] = 1
            
        res = []
        #seen = set()
        for word in words:
            #reset dict and seen for each new word
            #shallow copy
            pattern_map_dupe = copy.copy(pattern_map) 
            seen = set()
            if len(word) == len(pattern):
                i = 0
                for charw, charp in zip(word, pattern):
                    print(\"w: \", charw, \"p: \", charp)
                    print(pattern_map_dupe)
                    #subsequent encounter
                    if charw in seen:
                        if pattern_map_dupe[charp] != charw:
                            break
                    
                    #first encounter
                    #also must not be in seen already
                    elif pattern_map_dupe.get(charp, 0) == 1:
                        #don't want a=c, b=c
                        #must be one-to-one: a=a, b=c
                        if charw in seen:
                            break
                        else:
                            seen.add(charw)
                            pattern_map_dupe[charp] = charw
                    
                    #no match
                    else:
                        continue
                    i += 1

                if i == len(pattern):
                    res.append(word)
        return res
                    
        

class Solution:
    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
        def match(list1 , pattern):
            for i in range(len(pattern)):
                if list1[i] != pattern[i]:
                    return False
            return True
        
        def number_arr(list1):
            dict = {}
            arr = []
            last_given_value = 0
            for i in list1:
                if i not in dict:
                    last_given_value +=1
                    dict[i] = last_given_value
                    arr.append(dict[i])
                else:
                    arr.append(dict[i])
            return arr
        
        pat = number_arr(pattern)
        ans = []
        for word in words:
            word_list = number_arr(word)
            if match(pat , word_list):
                ans.append(word)
        return ans