⚡Flashcard Drill➔
NeetCode #516LC-291MediumBacktracking
← Back to All Problems

#516 · #291 · Word Pattern II(单词规律 II)

📌 Problem Statement & Constraints

Given a pattern string and a string s, return whether s matches the pattern, where each letter in the pattern maps bijectively to a non-empty substring of s. Constraints: 1 <= pattern.length, s.length <= 20.

💡 Core Algorithmic Approaches

  1. Backtrack over the pattern and the string simultaneously.
  2. If the current pattern letter already has a mapping, the substring at that position must equal it exactly.
  3. Otherwise, try every non-empty substring and require that it is not already mapped to another letter (bijection).
  4. Two maps are needed conceptually -- pattern-to-substring and substring-to-pattern -- and a set for the used substrings covers the reverse direction.

💻 Benchmark Python3 Implementation

class Solution:
    def wordPatternMatch(self, pattern: str, s: str) -> bool:
        def dfs(pi: int, si: int, fwd: dict, used: set) -> bool:
            if pi == len(pattern):
                return si == len(s)        # both consumed
            ch = pattern[pi]
            if ch in fwd:
                w = fwd[ch]
                if not s.startswith(w, si):
                    return False
                return dfs(pi + 1, si + len(w), fwd, used)
            for end in range(si + 1, len(s) + 1):
                w = s[si:end]
                if w in used:              # must be a bijection
                    continue
                fwd[ch] = w
                used.add(w)
                if dfs(pi + 1, end, fwd, used):
                    return True
                del fwd[ch]                # backtrack
                used.remove(w)
            return False

        return dfs(0, 0, {}, set())

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(2^n) in the worst case, bounded by the number of ways to cut s.
💾 Space Complexity
O(n) for the recursion plus the maps.

⚠️ Interview Pitfalls & Follow-ups

  • Using only the forward map: two different pattern letters could map to the same substring, violating the bijection.
  • Trying empty substrings: each mapping must be non-empty.
  • Forgetting startswith(w, si): the existing mapping must match at the current position, not merely appear somewhere.
  • Not backtracking the maps: later branches would see stale mappings.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Backtracking Problems