Domain 2MediumCORE

Word Pattern II

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.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Backtracking

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:

  1. Bijectivity: Every character in pattern must map to exactly one unique substring in s, and every used substring in s must 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).
  2. 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 (O(2N)O(2^N) 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:

  1. We iterate through s and the current character of pattern.
  2. If a pattern char has already been mapped (e.g., 'a' -> "hello"), we verify if the substring in s matches that stored value exactly at our current position.
  3. If it’s unmapped, we try every possible length for this segment starting from the current index of s.
  4. 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:

  1. State: We maintain two indices (p_idx for pattern, s_idx for string). We also need a dictionary pattern_map storing char -> substring and a set used_strings to enforce bijection efficiently (O(1)O(1) lookup).
  2. Base Case: If both p_idx reaches the end of pattern AND s_idx reaches the end of s, we found a valid match (return True). Otherwise, if one ends before the other but not simultaneously, return False (mismatch in length or content).
  3. Recursive Step:
    • Let current pattern char be char.
    • If char is already mapped: Check if substring of s starting at s_idx matches the stored value. Advance both indices by that string’s length + verify match. Return result of recursion or False immediately on mismatch.
    • If char is not mapped: Iterate through all possible lengths for this segment (from 1 to remaining characters in s).
      • 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).

Complexity Analysis

  • Time Complexity: In the worst case without pruning, checking every split point is exponential. However, with N≤20N \le 20, and strong pruning via used_strings set, this passes easily. Roughly bounded by trying all partitions of string length relative to pattern characters. Given constraints (L=20L=20), it’s well within limits for backtracking solutions.
  • Space Complexity: O(N)O(N) 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 == len checks 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., if target is “abc”, it consumes exactly 3 chars).
  • Length Mismatch: If pattern finishes but string remains, or vice versa, the base case returns False.