290. Word Pattern

Hash Table, String · 13 Dec 2023

Problem Statement

link: LeetCode.cn LeetCode

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:

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

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

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

Solution Approach

This problem can be efficiently solved by utilizing two dictionaries to establish a bijection between each character in the pattern and each word in the string.

Algorithm

Split the string s into individual words and initialize two empty dictionaries, dic1 and dic2, to store mappings between characters and words.
Iterate through each character p in pattern and each word w in the list of words simultaneously:
If all mappings are consistent without any discrepancies, return True, indicating that s follows the same pattern as pattern.

Implement

    class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
      s = s.split(" ")
      dic1, dic2 = {}, {}
      if len(pattern) != len(s):
        return False
      for p, w in zip(pattern, s):
        if p not in dic1:
          dic1[p] = w
        elif dic1[p] != w:
          return False
        if w not in dic2:
          dic2[w] = p
        elif dic2[w] != p:
          return False
      return True