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

Match Substring After Replacement

Difficulty: Hard

Problem Description

You are given two strings s and sub. You are also given a 2D character array mappings where mappings[i] = [old_i, new_i] indicates that you may perform the following operation any number of times: Replace a character old_i of sub with new_i. Each character in sub cannot be replaced more than once. Return true if it is possible to make sub a substring of s by replacing zero or more characters according to mappings. Otherwise, return false. A substring is a contiguous non-empty sequence of characters within a string.

Key Insights

  • The problem requires checking if a modified version of the string sub can be found within the string s.
  • We can replace characters in sub according to the given mappings, but each character can only be replaced once.
  • We need to consider all possible character replacements and efficiently check for the existence of modified sub in s.

Space and Time Complexity

Time Complexity: O(n * m), where n is the length of s and m is the length of sub, considering the worst-case scenario where we check each substring of s against all possible replacements of sub.

Space Complexity: O(k), where k is the number of mappings, to store the replacement pairs and the modified characters.

Solution

The solution involves creating a mapping of characters in sub to their possible replacements using a hash map. For each character in sub, we check if it can either match itself or one of its mapped replacements. We then slide through the string s, checking each substring of the same length as sub to see if it can match the modified version of sub.

  1. Create a mapping of characters from sub to their possible replacements.
  2. Iterate over all possible substrings of s that have the same length as sub.
  3. For each substring, compare it against the modified sub using the mapping.
  4. If a match is found, return true; if no matches are found after checking all substrings, return false.

Code Solutions

def matchSubstringAfterReplacement(s: str, sub: str, mappings: List[List[str]]) -> bool:
    from collections import defaultdict
    
    # Create a mapping from characters in sub to their possible replacements
    replace_map = defaultdict(set)
    for old, new in mappings:
        replace_map[old].add(new)
    
    # Add each character to its own replacement set
    for char in sub:
        replace_map[char].add(char)
    
    # Function to check if a substring can match sub
    def canMatch(sub_candidate):
        for i in range(len(sub)):
            if sub_candidate[i] not in replace_map[sub[i]]:
                return False
        return True
    
    # Check each substring of s
    for i in range(len(s) - len(sub) + 1):
        if canMatch(s[i:i + len(sub)]):
            return True
    
    return False
← Back to All Questions