sub to be replaced at most once according to the mapping. We use a mapping set for fast lookup.

Approach

Build a set of allowed replacements from mappings for O(1) lookup.
For each window of length len(sub) in s:
- For each character in sub, check if it matches the corresponding character in s, or if it can be replaced (using the mapping) to match.
- If all characters match for a window, return true.
If no window matches, return false.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    bool matchReplacement(string s, string sub, vector<vector<char>>& mappings) {\n        unordered_map<char, unordered_set<char>> mp;\n        for (auto& m : mappings) mp[m[0]].insert(m[1]);\n        int n = s.size(), m = sub.size();\n        for (int i = 0; i + m <= n; ++i) {\n            bool ok = true;\n            for (int j = 0; j < m; ++j) {\n                if (s[i+j] == sub[j]) continue;\n                if (!mp.count(sub[j]) || !mp[sub[j]].count(s[i+j])) {\n                    ok = false;\n                    break;\n                }\n            }\n            if (ok) return true;\n        }\n        return false;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    bool</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> matchReplacement</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">string</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> s&#

Related Tags