# [LeetCode] Top Interview 150 Problems Solving # 290 Word Pattern

# **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.

```python
# 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
    

```python
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.