from collections import defaultdict
import re

class Solution:
    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:
        reachable = defaultdict(set)
        for a, b in mappings:
            reachable[a].add(b)
        for c in sub:
            reachable[c].add(c)
        regex = ""
        for c in sub:
            if len(reachable[c]) > 1:
                regex += "("
                regex += "|".join(reachable[c])
                regex += ")"
            else:
                regex += c
        return re.compile(regex).search(s)
class Solution {
    public boolean matchReplacement(String s, String sub, char[][] mappings) {
        HashMap<Character, HashSet<Character>> m = new HashMap<>();
        for(char[] carr: mappings) {
            if (!m.containsKey(carr[0])){
                m.put(carr[0], new HashSet<Character>());
            }
            m.get(carr[0]).add(carr[1]);
        }
        int len_s = s.length();
        int len_sub = sub.length();
        for (int pos = 0; pos < s.length(); pos++ ){
            int i = pos;
            int j = 0;
            boolean cont = false; 
            while (j <= sub.length()) {
                if ( j == sub.length()) return true;
                int lenlefts = len_s - i;
                int lenleftsub = len_sub - j;
                if (lenlefts < lenleftsub) {
                    break;
                } else if ((s.charAt(i) == sub.charAt(j)) || 
				              (m.containsKey(sub.charAt(j)) && m.get(sub.charAt(j)).contains( s.charAt(i)))) {
                    i += 1;
                    j += 1;
                } else {
                    break;
                }
            }
        }
        return false;
    }
}
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 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.

&nbsp;
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.



&nbsp;
Constraints:


	1 &lt;= sub.length &lt;= s.length &lt;= 5000
	0 &lt;= mappings.length &lt;= 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.


var matchReplacement = function(s, sub, mappings) {
    let n= s.length;
    let m = sub.length;
    let map = new Array(36).fill().map(_=>new Array(36).fill(0));
    for(let i=0;i<mappings.length;i++) {
        let [o,ne] = mappings[i];
        if(isNaN(o)) {
            o = (o.toUpperCase()).charCodeAt(0)-55;
        } else {
            o = parseInt(o);
        }
        
        if(isNaN(ne)) {
            ne = (ne.toUpperCase()).charCodeAt(0)-55;
        } else {
            ne = parseInt(ne);
        }
        map[o][ne]=1;
    }
    // let map = new Map(mappings);
    for(let i=0;i<=n-m;i++) {
        let z=i;
        let j=0;
        while(j<m){
            if(s[z] !== sub[j]) {
                let ne = s[z];
                let o = sub[j];
                if(isNaN(o)) {
                    o = (o.toUpperCase()).charCodeAt(0)-55;
                } else {
                    o = parseInt(o);
                }

                if(isNaN(ne)) {
                    ne = (ne.toUpperCase()).charCodeAt(0)-55;
                } else {
                    ne = parseInt(ne);
                }
                if(map[o][ne] !== 1){
                    break;
                }
            }
            z++;
            j++;
        }
        if(j == m){
            return true
        }
    }
    return false
};
class Solution {
public:
    bool matchReplacement(string s, string sub, vector<vector<char>>& mappings) {

        int m(size(s)), n(size(sub));
        unordered_map<char, unordered_set<char>> mp;

        auto doit = [&](int ind) {

            for (int i=ind, j=0; i<ind+n; i++, j++) {
                if (s[i] == sub[j] or mp[sub[j]].count(s[i])) continue;
                return false;
            }
            return true;
        };

        for (auto& mapping : mappings) mp[mapping[0]].insert(mapping[1]);;
        for (int i=0; i<=m-n; i++) if (doit(i)) return true;
        return false;
    }
};