Problem Statement
Given a
pattern
and a string str
, find if str
follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in
pattern
and a non-empty word in str
.
Example 1:
Input: pattern ="abba"
, str ="dog cat cat dog"
Output: true
Example 2:
Input:pattern ="abba"
, str ="dog cat cat fish"
Output: false
Example 3:
Input: pattern ="aaaa"
, str ="dog cat cat dog"
Output: false
Example 4:
Input: pattern ="abba"
, str ="dog dog dog dog"
Output: false
Notes:
You may assume
You may assume
pattern
contains only lowercase letters, and str
contains lowercase letters that may be separated by a single space.Problem link
Video Tutorial
You can find the detailed video tutorial hereThought 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.
Ref: https://en.wikipedia.org/wiki/Injective_function |
Solutions
Encode string and patterns then compare
Time Complexity: O(N), N is the length of pattern or string array, we loop it 3 times, but still O(N)Space Complexity: O(N), N is the length of pattern or string array, we need the extra map and string to store the results
Use bijection mapping (Recommended)
There is also a clever implementation like below. The key point is use the index to compare, if there is duplicate index, meaning there are two keys already mapped to the same value. Also, remember java put() returns a valid, not a void :)
Time Complexity: N is the length of pattern or string array
Space Complexity: O(N), N is the length of pattern or string array, we need a map regardless