291. Word Pattern II
Model: qwen3.5:9b
Topics: Backtracking
FAANG asked: 1
Acceptance rate: 44.4%
Problem Breakdown
We are given a pattern string consisting of lowercase letters and a target string s. We need to determine if there exists a bijective mapping between the characters in pattern and substrings within s.
Key constraints:
- Bijectivity: Every character in
patternmust map to exactly one unique substring ins, and every used substring insmust be mapped by exactly one pattern character. No two different pattern chars can share the same string, nor can a single char split into multiple strings (it’s atomic). - Splitting: Unlike “Word Pattern I” where spaces define boundaries, here we don’t know where to cut
s. We must determine valid partition points dynamically during matching.
Intuition
If we try every possible way to segment s and check against the pattern, that’s brute force ( or worse). However, since mapping is consistent (if ‘a’ maps to “red” at index 0, any subsequent ‘a’ must also map to “red”), we can prune branches early.
The core insight is Backtracking with State:
- We iterate through
sand the current character ofpattern. - If a pattern char has already been mapped (e.g.,
'a' -> "hello"), we verify if the substring insmatches that stored value exactly at our current position. - If it’s unmapped, we try every possible length for this segment starting from the current index of
s. - Crucially, before assigning a new mapping (e.g.,
'b' -> "world"), we must check if"world"is already used by another character to satisfy bijection.
Approach
We will use Depth-First Search (DFS) with backtracking:
- State: We maintain two indices (
p_idxfor pattern,s_idxfor string). We also need a dictionarypattern_mapstoring char -> substring and a setused_stringsto enforce bijection efficiently ( lookup). - Base Case: If both
p_idxreaches the end ofpatternANDs_idxreaches the end ofs, we found a valid match (return True). Otherwise, if one ends before the other but not simultaneously, return False (mismatch in length or content). - Recursive Step:
- Let current pattern char be
char. - If
charis already mapped: Check if substring ofsstarting ats_idxmatches the stored value. Advance both indices by that string’s length + verify match. Return result of recursion or False immediately on mismatch. - If
charis not mapped: Iterate through all possible lengths for this segment (from 1 to remaining characters ins).- Extract candidate substring.
- Check if candidate exists in
used_strings. If yes, skip (bijection violation). - Else, add mapping (
pattern_map[char] = sub) and mark as used. Recurse with updated indices.
- Backtrack: After returning from recursion, remove the mapping to allow other branches to try different lengths for this character or map it differently if needed (though typically once mapped in a valid branch we keep it until failure).
- Let current pattern char be
Complexity Analysis
- Time Complexity: In the worst case without pruning, checking every split point is exponential. However, with , and strong pruning via
used_stringsset, this passes easily. Roughly bounded by trying all partitions of string length relative to pattern characters. Given constraints (), it’s well within limits for backtracking solutions. - Space Complexity: for the recursion stack depth (max 20) and storage for
pattern_map/used_strings.
Solution
class Solution:
def wordPatternMatch(self, pattern: str, s: str) -> bool:
# Mapping from char to string segment
mapping = {}
# Set of strings already used by other characters (for bijection check)
used_strings = set()
def backtrack(p_idx, s_idx):
# If we've consumed the entire pattern and string simultaneously
if p_idx == len(pattern) and s_idx == len(s):
return True
# If one is exhausted but not both, mismatch in length/content
if p_idx >= len(pattern) or s_idx >= len(s):
return False
current_char = pattern[p_idx]
# Case 1: Character already mapped to a string segment
if current_char in mapping:
target_str = mapping[current_char]
# Check if the substring matches what we expect
remaining_s_len = len(s) - s_idx
# If there isn't enough space left, or content doesn't match
if not (s[s_idx:s_idx + len(target_str)] == target_str):
return False
# Advance indices by length of the mapped string
return backtrack(p_idx + 1, s_idx + len(target_str))
else:
# Case 2: Character is unmapped. Try all possible segment lengths.
for i in range(s_idx + 1, len(s) + 1):
candidate = s[s_idx:i]
# Check bijection constraint before mapping new string
if candidate not in used_strings and current_char not in mapping:
# Map the character to this segment temporarily
mapping[current_char] = candidate
used_strings.add(candidate)
# Recurse with updated indices
if backtrack(p_idx + 1, i):
return True
# Backtrack: Unmap so other branches can try different lengths or mappings
del mapping[current_char]
used_strings.remove(candidate)
return False
return backtrack(0, 0)
# Example usage for verification (not part of class method signature usually):
# sol = Solution()
# print(sol.wordPatternMatch("abab", "redblueredblue")) # True
Edge Cases Handled
- Empty Inputs: The constraints say length >= 1, but the logic handles
p_idx == lenchecks which cover empty pattern cases implicitly. If inputs were allowed to be empty (e.g., both ""), it returns True via base case. - Bijection Violation: Handled by checking
used_strings. If ‘a’ maps to “red”, and we try mapping ‘b’ to “red” later, the check fails immediately. - Partial Matches: The code checks exact substring equality (
s[s_idx:s_idx + len] == target_str). It does not allow partial overlaps (e.g., iftargetis “abc”, it consumes exactly 3 chars). - Length Mismatch: If pattern finishes but string remains, or vice versa, the base case returns False.