890. Find and Replace Pattern #

Problem #

Given a list of strings words and a string pattern, return a list of words[i] that match pattern. You may return the answer in any order.

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.

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.

Example 2:

Input: words = ["a","b","c"], pattern = "a"
Output: ["a","b","c"]

Constraints:

• 1 <= pattern.length <= 20
• 1 <= words.length <= 50
• words[i].length == pattern.length
• pattern and words[i] are lowercase English letters.

Problem Summary #

You have a list of words words and a pattern  pattern, and you want to know which words in words match the pattern. If there exists a permutation of letters p such that after replacing every letter x in the pattern with p(x), we get the desired word, then the word matches the pattern. (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 the list of words in words that match the given pattern. You may return the answer in any order.

Solution Approach #

• According to the problem requirements, map the two strings separately: map each letter of a string in the words string array to each letter of the pattern string. Use a map to store this. The problem also requires that there must not be two letters mapping to the same letter, so add another map to determine whether the current letter has already been mapped. If both of the above two conditions are satisfied, it means the pattern matches. Finally, output all strings that satisfy the pattern match.

Code #

package leetcode

func findAndReplacePattern(words []string, pattern string) []string {
	res := make([]string, 0)
	for _, word := range words {
		if match(word, pattern) {
			res = append(res, word)
		}
	}
	return res
}

func match(w, p string) bool {
	if len(w) != len(p) {
		return false
	}
	m, used := make(map[uint8]uint8), make(map[uint8]bool)
	for i := 0; i < len(w); i++ {
		if v, ok := m[p[i]]; ok {
			if w[i] != v {
				return false
			}
		} else {
			if used[w[i]] {
				return false
			}
			m[p[i]] = w[i]
			used[w[i]] = true
		}
	}
	return true
}