Solution Explanation for LeetCode 2301. Match Substring After Replacement

This problem asks whether a given substring sub can be made into a substring of string s after applying a series of character replacements defined in mappings. Each character in sub can be replaced at most once.

Both solutions presented leverage a similar strategy:

1. Create a Replacement Mapping: This step efficiently stores the allowed character replacements. Solution 1 uses a hash table (dictionary in Python, HashMap in Java, unordered_map in C++, map in Go), while Solution 2 uses a 2D boolean array to represent the replacement possibilities. The array approach is slightly more efficient in space and access time for this problem, as it avoids the overhead of hash table lookups and only needs to deal with ASCII characters (128 possible values).

2. Enumerate Substrings: The code iterates through all possible substrings of s that have the same length as sub.

3. Check for Match: For each substring, it verifies if it can be obtained from sub by applying the replacements from the mapping. This check involves comparing each character in the substring with the corresponding character in sub. If the characters differ, it checks if the replacement is valid based on the mapping.

4. Return Result: If a match is found (substring can be made from sub), the function immediately returns true. If no match is found after checking all substrings, it returns false.

Time Complexity Analysis

Both solutions have the same time complexity: O(m*n), where:

• m is the length of the string s.
• n is the length of the substring sub.

The nested loops (iterating through substrings and characters within substrings) dominate the runtime. The creation of the replacement mapping is O(k) where k is the number of mappings, which is significantly less than m*n.

Space Complexity Analysis

• Solution 1 (Hash Table): O(k + C^2), where k is the number of mappings and C is the size of the character set (number of unique characters in s and sub). The hash table's space usage is proportional to the number of unique characters in mappings and their replacements. In the worst case, if all characters have replacement characters, it becomes O(C^2).

• Solution 2 (Array): O(C^2). The 2D boolean array consumes a fixed amount of space determined by the character set size (128x128 in this case). This solution has a more predictable and consistently smaller space complexity compared to using hash tables.

Code Examples (with explanations inline)

Solution 1 (Hash Table based):

from collections import defaultdict
 
class Solution:
    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:
        # Create a replacement mapping using a defaultdict (avoids KeyError exceptions)
        replacement_map = defaultdict(set)
        for old, new in mappings:
            replacement_map[old].add(new)
 
        # Iterate through all substrings of s with the length of sub
        for i in range(len(s) - len(sub) + 1):
            substring = s[i:i + len(sub)]  # Extract the substring
            is_match = True
            for j in range(len(sub)):  # Compare the substring with sub, checking for valid replacements
                if substring[j] != sub[j] and substring[j] not in replacement_map[sub[j]]:
                    is_match = False
                    break  # No need to continue checking if there's an invalid replacement
            if is_match:
                return True  # Found a match
 
        return False  # No match found

Solution 2 (Array based):

class Solution:
    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:
        # Create a 2D boolean array for replacements (more efficient for ASCII characters)
        replacement_array = [[False] * 128 for _ in range(128)] # Initialize a 128x128 array
        for old, new in mappings:
            replacement_array[ord(old)][ord(new)] = True
 
        # Iterate through all substrings of s with the length of sub and perform the match
        for i in range(len(s) - len(sub) + 1):
            substring = s[i:i + len(sub)]
            is_match = True
            for j in range(len(sub)):
                if substring[j] != sub[j] and not replacement_array[ord(sub[j])][ord(substring[j])]:
                    is_match = False
                    break
            if is_match:
                return True
        return False

The Java, C++, and Go versions would follow a similar structure, using the respective data structures (HashMap/unordered_map/map for Solution 1 and 2D boolean array for Solution 2). The core logic of substring enumeration and replacement checking remains consistent across all languages.