Solution


Approach 1: Two Maps

Intuition and Algorithm

If say, the first letter of the pattern is "a", and the first letter of the word is "x", then in the permutation, "a" must map to "x".

We can write this bijection using two maps: a forward map and a backwards map .

Then, if there is a contradiction later, we can catch it via one of the two maps. For example, if the (word, pattern) is ("aa", "xy"), we will catch the mistake in (namely, ). Similarly, with (word, pattern) = ("ab", "xx"), we will catch the mistake in .

Complexity Analysis

  • Time Complexity: , where is the number of words, and is the length of each word.

  • Space Complexity: , the space used by the answer.


Approach 2: One Map

Intuition and Algorithm

As in Approach 1, we can have some forward map , where is the set of letters.

However, instead of keeping track of the reverse map , we could simply make sure that every value in the codomain is reached at most once. This would guarantee the desired permutation exists.

So our algorithm is this: after defining in the same way as Approach 1 (the forward map of the permutation), afterwards we make sure it reaches distinct values.

Complexity Analysis

  • Time Complexity: , where is the number of words, and is the length of each word.

  • Space Complexity: , the space used by the answer.


Analysis written by: @awice.