You are given two strings s and sub. You are also given a 2D character array mappings where mappings[i] = [oldi, newi] indicates that you may perform the following operation any number of times:
oldi of sub with newi.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.
Example 1:
Input: s = "fool3e7bar", sub = "leet", mappings = [["e","3"],["t","7"],["t","8"]] Output: true Explanation: Replace the first 'e' in sub with '3' and 't' in sub with '7'. Now sub = "l3e7" is a substring of s, so we return true.
Example 2:
Input: s = "fooleetbar", sub = "f00l", mappings = [["o","0"]] Output: false Explanation: The string "f00l" is not a substring of s and no replacements can be made. Note that we cannot replace '0' with 'o'.
Example 3:
Input: s = "Fool33tbaR", sub = "leetd", mappings = [["e","3"],["t","7"],["t","8"],["d","b"],["p","b"]] Output: true Explanation: Replace the first and second 'e' in sub with '3' and 'd' in sub with 'b'. Now sub = "l33tb" is a substring of s, so we return true.
Constraints:
1 <= sub.length <= s.length <= 50000 <= mappings.length <= 1000mappings[i].length == 2oldi != newis and sub consist of uppercase and lowercase English letters and digits.oldi and newi are either uppercase or lowercase English letters or digits.Problem Overview: You receive a string s, a pattern sub, and a list of allowed character replacements. Each pair (a, b) means character a in the pattern may be replaced with b when matching. The goal is to determine whether sub can match any substring of s after applying these allowed replacements.
Approach 1: Direct Mapping and Iterative Check (Time: O(n * m), Space: O(k))
Store all replacement rules in a hash-based lookup structure such as HashMap<char, Set<char>>. Each key represents a pattern character and the set contains characters it may transform into. Then iterate through every possible starting index in s. For each index, compare the substring of length m with sub character by character.
At position j, the characters match if either s[i + j] == sub[j] or the mapping allows sub[j] to transform into s[i + j]. If any position fails both checks, break early and move to the next starting index. This approach relies on constant‑time hash table lookups and straightforward string iteration. The early exit significantly reduces average runtime in practice.
Approach 2: Optimized Trie-Based Matching (Time: O(n + m * Σ), Space: O(n * Σ))
A more structured approach builds a trie from substrings of s. Each path in the trie represents a possible sequence of characters from the source string. While matching the pattern, you traverse the trie but allow multiple outgoing edges when replacements are possible.
For each character sub[j], the algorithm considers the direct match and every character reachable through the replacement map. The trie lets you branch efficiently while pruning impossible paths early. This reduces redundant substring comparisons that occur in the naive scan. The technique combines prefix sharing with controlled branching, a common optimization in advanced string matching systems.
This method performs well when the input string is large or when many substring checks would otherwise repeat similar prefix comparisons.
Recommended for interviews: The direct mapping with iterative substring checking is the expected solution. It demonstrates correct modeling of the replacement rules using a hash map and efficient early termination during comparisons. The trie approach shows deeper knowledge of string matching optimizations, but most interviewers expect the hash‑map scanning solution first because it is simpler and already meets typical constraints.
This approach involves creating a mapping of characters from `sub` to possible replacements according to the `mappings` array. Then, iterate over all possible substrings of `s` of the length of `sub` and check if any transformation of `sub` matches the current substring of `s`.
We first parse the `mappings` to build a dictionary where each character points to a set of possible replacements (including itself). As we slide a window equal to the size of `sub` over `s`, we check if we can replace `sub` into that substring using our replacements mappings.
In this C solution, we define a boolean 2D array for possible character transformations including self-transformations. For each substring of `s` of the same length as `sub`, we check whether `sub` can be transformed into it. This approach ensures each character can still be a match for the original character itself.
Time Complexity: O((s.length - sub.length) * sub.length * |Σ|), where |Σ| is the character set size (here assumed to be 256).
Space Complexity: O(|Σ| * |Σ|) for storing transformation relationships.
This approach involves building a Trie structure from the substrings of `s` and leveraging potential transformations of the `sub` string to search efficiently within the Trie. Each character in `sub` can be replaced by its possible transformations to find matching paths in the Trie built from `s`.
The Trie allows for quick searching through potential transformations and reduces redundant checks, focusing on viable paths through possible substrings of `s`. It addresses matching patterns effectively by exploring only valid substitution pathways within the Trie structure.
This C solution builds a Trie from substrings of `s`, and employs transformation mapping during Trie traversal using a recursive search function. Each character in the Trie can potentially represent a transformed character from `sub`, facilitating efficient substring checking via the Trie data structure.
Time Complexity: O(n * m * t), where `n` is the length of `sub`, `m` is the length of `s`, and `t` is the potential mapping transformation choices.
Space Complexity: O(m * n).
First, we use a hash table d to record the set of characters that each character can be replaced with.
Then we enumerate all substrings of length sub in s, and judge whether the string sub can be obtained by replacement. If it can, return true, otherwise enumerate the next substring.
At the end of the enumeration, it means that sub cannot be obtained by replacing any substring in s, so return false.
The time complexity is O(m times n), and the space complexity is O(C^2). Here, m and n are the lengths of the strings s and sub respectively, and C is the size of the character set.
Since the character set only contains uppercase and lowercase English letters and numbers, we can directly use a 128 times 128 array d to record the set of characters that each character can be replaced with.
The time complexity is O(m times n), and the space complexity is O(C^2).
| Approach | Complexity |
|---|---|
| Using Direct Mapping and Iterative Check | Time Complexity: O((s.length - sub.length) * sub.length * |Σ|), where |Σ| is the character set size (here assumed to be 256). |
| Optimized Trie-Based Matching | Time Complexity: O(n * m * t), where `n` is the length of `sub`, `m` is the length of `s`, and `t` is the potential mapping transformation choices. |
| Hash Table + Enumeration | — |
| Array + Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Mapping and Iterative Check | O(n * m) | O(k) | General solution. Works well when pattern length is moderate and mapping lookups are constant time. |
| Trie-Based Matching | O(n + m * Σ) | O(n * Σ) | Useful when many substring comparisons share prefixes or when repeated matching queries occur. |
Leetcode BiWeekly contest 80 Match Substring After Replacement • Prakhar Agrawal • 1,015 views views
Watch 2 more video solutions →Practice Match Substring After Replacement with our built-in code editor and test cases.
Practice on FleetCode