290. Word Pattern

📋 Đề Bài

Given a pattern and a string s, find if s 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 s.

Example 1:

Input: pattern = "abba", s = "dog cat cat dog"
Output: true

Example 2:

Input: pattern = "abba", s = "dog cat cat fish"
Output: false

Example 3:

Input: pattern = "aaaa", s = "dog cat cat dog"
Output: false

Constraints:

1 <= pattern.length <= 300
pattern contains only lower-case English letters.
1 <= s.length <= 3000
s contains only lowercase English letters and spaces ' '.
s does not contain any leading or trailing spaces.
All the words in s are separated by a single space.

🧠 Thuật Toán & Kỹ Thuật

Hash Table (Bảng băm)

⏱️ Thời gian O(n)

💾 Không gian O(n)

💻 Lời Giải

Python 0290-word-pattern.py

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        m1 = defaultdict(int)
        m2 = defaultdict(int)
        n = len(pattern)
        s = s.split()
        
        if n != len(s):
            return False
        
        for i in range(n):
            if m1[pattern[i]] != m2[s[i]]:
                return False
            m1[pattern[i]] = i + 1
            m2[s[i]] = i + 1
            
        return True