We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Word Pattern II

Number: 291

Difficulty: Medium

Paid? Yes

Companies: Microsoft, Apple, Oracle, Snowflake, Dropbox, Uber

Problem Description

Given a pattern string and a string s, determine if s can be segmented such that each character in the pattern maps to a non-empty substring of s. The mapping must be bijective, meaning no two characters may map to the same substring and each mapping is unique.

Key Insights

  • Use recursive backtracking to explore all potential mappings from pattern characters to substrings in s.
  • Maintain two structures: one (e.g., a hash map) for mapping pattern characters to substrings and another (e.g., a set) to track substrings that have already been assigned.
  • For each character in the pattern, if it is already mapped, check if the corresponding part of s matches the mapped substring.
  • For unmapped characters, try every possible non-empty substring starting at the current index in s, and backtrack upon failure.
  • Ensure both the pattern and s are completely used to validate a successful mapping.

Space and Time Complexity

Time Complexity: Worst-case exponential, approximately O(n^m) where n is the length of s and m is the length of the pattern, due to exploring various substring splits. Space Complexity: O(m + n) representing the recursion depth and the space for storing the mapping and used substrings.

Solution

The solution uses recursive backtracking. We use a hash map to map each character in the pattern to a candidate substring from s, and a hash set to ensure each substring is used only once. At each step, if a character already has a mapping, we verify that the next segment of s matches that mapping; if not, we try all possible substring splits for an unmapped character. This systematic exploration guarantees that we eventually find a valid bijective mapping if one exists.

Code Solutions

# Python solution using backtracking

def wordPatternMatch(pattern: str, s: str) -> bool:
    def backtrack(p_index, s_index, mapping, used):
        # If both pattern and s are fully processed, return True
        if p_index == len(pattern) and s_index == len(s):
            return True
        # If one is finished and the other is not, return False
        if p_index == len(pattern) or s_index == len(s):
            return False
        
        current_char = pattern[p_index]
        
        # If the character is already mapped, check the corresponding substring in s
        if current_char in mapping:
            word = mapping[current_char]
            if not s.startswith(word, s_index):
                return False
            return backtrack(p_index + 1, s_index + len(word), mapping, used)
        
        # Try all possible substrings starting from s_index
        for end in range(s_index + 1, len(s) + 1):
            candidate = s[s_index:end]
            # Skip if candidate substring is already mapped to another character
            if candidate in used:
                continue
            mapping[current_char] = candidate
            used.add(candidate)
            # Recursive call to check subsequent pattern and string
            if backtrack(p_index + 1, end, mapping, used):
                return True
            # Backtrack if mapping doesn't lead to a solution
            del mapping[current_char]
            used.remove(candidate)
        return False

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

# Example Usage:
# print(wordPatternMatch("abab", "redblueredblue"))
← Back to All Questions