291. Word Pattern II - Detailed Explanation

Problem Statement

Given a pattern and a string, determine if the string follows the same pattern. In this context, "following the pattern" means there exists a bijective mapping between each character in the pattern and a non-empty substring of the string. In other words, every pattern character maps to a unique substring, and that mapping, when applied, should recreate the original string exactly.

Examples

Example 1

• Input: pattern = "abab", s = "redblueredblue"
• Output: true
• Explanation:
  A possible mapping is:
  • 'a' → "red"
  • 'b' → "blue"
    Replacing the characters in the pattern with their corresponding substrings gives "redblueredblue", which matches the input string.

Example 2

• Input: pattern = "aaaa", s = "asdasdasdasd"
• Output: true
• Explanation:
  A possible mapping is:
  • 'a' → "asd"
    Repeating "asd" four times gives "asdasdasdasd".

Example 3

• Input: pattern = "aabb", s = "xyzabcxzyabc"
• Output: false
• Explanation:
  No valid bijective mapping exists that can reconstruct the string from the pattern.

Constraints

• The pattern contains only lower-case English letters.
• The string consists of lower-case English letters.
• The lengths of the pattern and the string are within reasonable limits (typically pattern length is much smaller than the string length).

Hints

1. Backtracking is Your Friend:
   Think about assigning a substring to a pattern character and then recursively checking if the rest of the pattern can match the remaining string. If it doesn’t work, backtrack and try a different assignment.

2. Maintain a Mapping and a Set:
   Use a hash map (or dictionary) to store the mapping of pattern characters to substrings and a set to keep track of which substrings have already been used. This ensures that no two characters map to the same substring (bijective mapping).

Approach Overview

Brute Force Approach (Recursive Backtracking)

• Idea:
  For each character in the pattern that is not yet mapped, try every possible non-empty substring of the string starting from the current index as its mapping.
• Process:
  • If the current pattern character is already mapped, check if the corresponding substring in the string matches the mapping.
  • If it does, recursively process the next character in the pattern and the next segment in the string.
  • If it doesn’t match, or if the recursion fails, backtrack and try a different substring assignment.
• Outcome:
  Return true if a complete valid mapping is found that exactly reconstructs the string; otherwise, return false.

Optimal Approach (Using Backtracking with Pruning)

• Idea:
  The optimal approach is still based on recursion, but by using a mapping and a set, you prune many unnecessary recursive calls.
• Advantages:
  • Efficiently checks for mapping conflicts.
  • Avoids redundant computations by immediately abandoning invalid mappings.

Detailed Step-by-Step Explanation

1. Initialize Mapping and Used Set:
   Create an empty dictionary (or HashMap) to map pattern characters to substrings and an empty set to track the substrings that are already in use.

2. Recursive Function (Backtracking):

   • Base Case:
     If you have reached the end of the pattern and the end of the string simultaneously, return true.
   • If the Pattern Character is Already Mapped:
     • Retrieve the mapped substring.
     • Check if the string from the current index starts with this substring.
     • If yes, move the index forward by the length of the substring and continue recursively.
     • If not, return false immediately.
   • If the Pattern Character is Not Mapped:
     • Iterate over possible end indices for the substring (starting from the current index + 1).
     • For each substring candidate, check if it’s already used. If not, add it to the mapping and mark it as used.
     • Recursively attempt to solve the rest of the problem with the updated mapping.
     • If the recursive call returns true, the solution is found.
     • If not, remove the mapping (backtrack) and try the next substring.

3. Final Check:
   Return the result of the recursive function call initiated from the beginning of the pattern and the string.

Python Implementation