Baozi Training Blog (包子IT面试培训博客)

Baozi Training Blog (包子IT面试培训博客)

Thought Process

A very simple problem thus normally can solve it in multiple ways.
 

Encode string and patterns then compare

Since we are comparing "patterns" here, one straightforward way is encode the pattern into a string, then use the same encoding algorithm to encode the str array into a string, then compare the string.

What encoding should we choose? Well it's not really an encoding per se. What I did is just convert any word or character to a character staring with ('a' + an index). If we see this character before, we just directly return from the hash map lookup. For example, "duck dog dog" would be encoded as "abb" while "bcc" would also be encoded as "abb".

Use bijection mapping

Note in the problem description it mentions it is a bijection mapping (i.e., a one to one mapping).
As shown in the graph below, you see the differences between injection, surjection and bijection. That said, bijection does not allow duplicates. We can build a one to one mapping between the pattern and string, since it's bijection, if two characters in the pattern map to the same string, then it's not a valid bijection, therefore return false.

Read full article from Baozi Training Blog (包子IT面试培训博客)