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
- Backtrack over the pattern and the string simultaneously.
- If the current pattern letter already has a mapping, the substring at that position must equal it exactly.
- Otherwise, try every non-empty substring and require that it is not already mapped to another letter (bijection).
- 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.