💬 Discord
Sign In
NeetCode #57LC-290EasyArrays & Hashing
← Back to All Problems

#57 · #290 · Word Pattern(单词规律)

📌 Problem Statement & Constraints

Given a pattern string and a string s, determine whether s follows the same pattern: each letter of pattern must map bijectively to a whitespace-separated word of s. Constraints: 1 <= pattern.length <= 300, 1 <= s.length <= 3000; pattern contains only lowercase letters; s contains lowercase letters and spaces.

💡 Core Algorithmic Approaches

  1. Split s into words and compare the counts with pattern first.
  2. Then build a bijection in both directions, exactly as in Isomorphic Strings.
  3. The forward map ensures one letter always maps to the same word; the reverse map ensures two different letters cannot map to the same word.
  4. Both directions are required: pattern = "ab", s = "dog dog" must fail.

💻 Benchmark Python3 Implementation

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        words = s.split()
        if len(pattern) != len(words):
            return False
        fwd = {}                           # letter -> word
        rev = {}                           # word -> letter
        for ch, w in zip(pattern, words):
            if fwd.get(ch, w) != w or rev.get(w, ch) != ch:
                return False               # bijection violated
            fwd[ch] = w
            rev[w] = ch
        return True

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n + total characters): splitting is linear in s, and the pairing loop is linear in the number of words.
💾 Space Complexity
O(k) for the two maps and the word list.

⚠️ Interview Pitfalls & Follow-ups

  • Using only one map: pattern = "ab", s = "dog dog" would be wrongly accepted.
  • Forgetting the length check: unequal counts must fail, and zip would silently truncate.
  • Splitting on ' ' explicitly: s.split(' ') creates empty strings for repeated spaces; s.split() collapses runs of whitespace and is safer.
  • Comparing character frequencies instead of building a bijection: frequency equality is necessary but not sufficient.