Understanding the Problem

There are two strings given. One is pattern, and another one is a string with spaces. If the pattern is ”abba” and the string is ”dog cat cat dog”, the first index ”a” takes ”dog”, the second index ”b” takes ”cat”, the third index ”b” takes ”cat” again, the fourth index ”a” takes ”dog”. The ”a” all matches with ”dog” and all ”b” matches with ”cat”, so it returns True.

See the example below.

# example 1
Input: pattern = "abba", s = "dog cat cat dog"
Output: True

# example 2
Input: pattern = "abba", s = "dog cat dog dog"
Output: False

The second example returns False because ”b” patterns have two different values ”cat” and ”dog”, so the patterns do not have relative values.

Approach

It is a hashmap problem. I would use a hashmap and check if the keys values of each pattern match what is in the dictionary.

1. Use dictionary

2. loop the pattern and check the dictionary

Solution

I had to declare the dictionary first and fill it up one by one to check the next key and value of the patterns. For the exception, if the length of the pattern and s are not equal, I returned False.

The key to solving the problem is like this.

1. for looping with zip(pattern, s.split()) to check key and value in pair

2. Get all values and keys of the dictionary in vals and keys

3. Check with conditions

• if the pattern is not in dictionary keys, and the value also is not in the values of the dictionary, simply add the key and value

• if the pattern is not in the keys of the dictionary, but the value is in the dictionary, the pattern does not match, so return False. For example, the dictionary is with key value as d = {"a": "dog"}, and the current pattern is ”b” with value ”dog”, the pattern does not match the current dictionary

• if pattern is in the keys of the dictionary and the value is not equal to its value, it returns False. For example, the dictionary has key value as d = {“a”": “dog”}, and the current pattern is “a” with value ”cat”, the pattern does not match

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        if len(pattern) != len(s.split()):
            return False

        d = {}

        for p, w in zip(pattern, s.split()):
            vals = d.values()
            keys = d.keys()

            if p not in keys and w not in vals:
                d[p] = w
            elif p not in keys and w in vals:
                return False
            elif p in keys and d[p] != w:
                return False
        return True

Reflection

It had O(n) complexity and the solution is pretty much okay I guess. It is just a bit making me feel uncomfortable with many elif conditions but other people also chose this way to solve the problem.