All problems

Find and Replace Pattern

Medium · hash map

You are given a list of lower-case words and a lower-case pattern. Every word has the same length as the pattern.

A word matches the pattern if you can swap each letter of the pattern for a letter so that you get exactly that word, where the swap follows two rules:

• the same pattern letter is always swapped for the same letter, and
• two different pattern letters are never swapped for the same letter.

For example, the pattern "xyx" matches "pop" (x becomes p, y becomes o), but not "aaa", because x and y would both have to become a, and not "fee", because the first x would become f and the second e.

Return the words that match, in the order they appear in words. A word that appears more than once is returned once for each appearance. If no word matches, return an empty list.

Examples

Example 1

Input: words = ["pop", "sos", "fee", "aaa", "dad"], pattern = "xyx"

Output: ["pop", "sos", "dad"]

"fee" and "aaa" break the rules: the first needs x to become two different letters, and the second makes x and y become the same letter.

Example 2

Input: words = ["xyz", "xxy", "pqr", "aba"], pattern = "abc"

Output: ["xyz", "pqr"]

The pattern has three different letters, so a matching word needs three different letters.

Example 3

Input: words = ["bb", "bc", "zz"], pattern = "aa"

Output: ["bb", "zz"]

Constraints

• 1 <= len(words) <= 10^4
• 1 <= len(pattern) <= 20
• len(words[i]) == len(pattern)
• Every word and the pattern contain only lower-case English letters.