README.md

290. Word Pattern

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

Note:

You may assume pattern contains only lowercase letters, and str contains lowercase letters that may be separated by a single space.

Solutions (Python)

1. Brute Force

class Solution:
    def wordPattern(self, pattern: str, str: str) -> bool:
        words = str.split()

        if len(pattern) != len(words):
            return False

        for i in range(len(pattern)):
            for j in range(i + 1, len(pattern)):
                if (pattern[j] == pattern[i]) != (words[j] == words[i]):
                    return False

        return True

2. HashMap

class Solution:
    def wordPattern(self, pattern: str, str: str) -> bool:
        words = str.split()

        if len(pattern) != len(words):
            return False

        match = {}
        used = set()

        for ch, wo in zip(pattern, words):
            if (ch in match) != (wo in used):
                return False
            elif ch not in match:
                match[ch] = wo
                used.add(wo)
            elif match[ch] != wo:
                return False

        return True