[LeetCode] Match Substring After Replacement

2301. Match Substring After Replacement

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 replace any number of oldi characters 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
bool matchReplacement(string s, string sub, vector<vector<char>>& mappings) {
unordered_map<char, unordered_set<char>> mp;
for(auto& m : mappings)
mp[m[0]].insert(m[1]);

int n = s.length(), m = sub.length();
for(int i = 0; i <= n - m; i++) {
int j;
for(j = 0; j < m; j++) {
if(sub[j] == s[i + j]) continue;
if(mp.count(sub[j]) and mp[sub[j]].count(s[i + j])) continue;
break;
}
if(j == m) return true;
}


return false;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/06/12/PS/LeetCode/match-substring-after-replacement/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.