##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2301.html

# 2301. Match Substring After Replacement

• Difficulty: Hard.
• Related Topics: Array, Hash Table, String, String Matching.
• Similar Questions: Design Add and Search Words Data Structure.

## Problem

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:

• Replace a character 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 <= 5000

• 0 <= mappings.length <= 1000

• mappings[i].length == 2

• oldi != newi

• s and sub consist of uppercase and lowercase English letters and digits.

• oldi and newi are either uppercase or lowercase English letters or digits.

## Solution

• class Solution {
private char[] c1;
private char[] c2;
private Set<Character>[] al;

public boolean matchReplacement(String s, String sub, char[][] mappings) {
c1 = s.toCharArray();
c2 = sub.toCharArray();
al = new Set[75];
for (int i = 0; i < 75; i++) {
Set<Character> temp = new HashSet<>();
al[i] = temp;
}
for (char[] mapping : mappings) {
}
return ans(c1.length, c2.length) == 1;
}

private int ans(int m, int n) {
if (m == 0) {
return 0;
}
if (ans(m - 1, n) == 1) {
return 1;
}
if (m >= n && (c1[m - 1] == c2[n - 1] || al[c2[n - 1] - '0'].contains(c1[m - 1]))) {
while (n >= 1 && (c1[m - 1] == c2[n - 1] || al[c2[n - 1] - '0'].contains(c1[m - 1]))) {
n--;
m--;
}
if (n == 0) {
return 1;
}
}
return 0;
}
}

############

class Solution {
public boolean matchReplacement(String s, String sub, char[][] mappings) {
Map<Character, Set<Character>> d = new HashMap<>();
for (var e : mappings) {
}
int m = s.length(), n = sub.length();
for (int i = 0; i < m - n + 1; ++i) {
boolean ok = true;
for (int j = 0; j < n && ok; ++j) {
char a = s.charAt(i + j), b = sub.charAt(j);
if (a != b && !d.getOrDefault(b, Collections.emptySet()).contains(a)) {
ok = false;
}
}
if (ok) {
return true;
}
}
return false;
}
}

• class Solution:
def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:
d = defaultdict(set)
for a, b in mappings:
for i in range(len(s) - len(sub) + 1):
if all(a == b or a in d[b] for a, b in zip(s[i : i + len(sub)], sub)):
return True
return False

############

# 2301. Match Substring After Replacement
# https://leetcode.com/problems/match-substring-after-replacement

class Solution:
def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:
mp = defaultdict(set)
n, m = len(s), len(sub)

for a, b in mappings:

def go(index, curr):
if curr == m:
return True

if index == n:
return False

if sub[curr] == s[index] or sub[curr] in mp[s[index]]:
return go(index + 1, curr + 1)

return False

for i in range(n):
if i + m <= n and go(i, 0):
return True

return False


• class Solution {
public:
bool matchReplacement(string s, string sub, vector<vector<char>>& mappings) {
unordered_map<char, unordered_set<char>> d;
for (auto& e : mappings) {
d[e[0]].insert(e[1]);
}
int m = s.size(), n = sub.size();
for (int i = 0; i < m - n + 1; ++i) {
bool ok = true;
for (int j = 0; j < n && ok; ++j) {
char a = s[i + j], b = sub[j];
if (a != b && !d[b].count(a)) {
ok = false;
}
}
if (ok) {
return true;
}
}
return false;
}
};

• func matchReplacement(s string, sub string, mappings [][]byte) bool {
d := [128][128]bool{}
for _, e := range mappings {
d[e[0]][e[1]] = true
}
for i := 0; i < len(s)-len(sub)+1; i++ {
ok := true
for j := 0; j < len(sub) && ok; j++ {
a, b := s[i+j], sub[j]
if a != b && !d[b][a] {
ok = false
}
}
if ok {
return true
}
}
return false
}


Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).