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

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures

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
					elif 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])
		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])
			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])
					elif 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]:

		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)
		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 = []
		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]:

		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