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.