[Solved] Match Substring After Replacement LeetCode Contest Problem

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.

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 {
public:
    bool matchReplacement(string s, string sub, vector<vector<char>>& mappings) {
        int n = sub.size(); int m = s.size();
        unordered_set<char> st;
        unordered_map<char, unordered_set<char>> mp;
        for(auto &c:sub){
            st.insert(c);
        }
        for(auto &cv:mappings){
            mp[cv[0]].insert(cv[1]);
            if(st.count(cv[0]))
                st.insert(cv[1]);
        }
        int j = 0;
        for(int i = 0; i<m; ++i){
			//not exist, reset
            if(!st.count(s[i])){
                j = 0;
                continue;
            }
			// equal or exist mapping, counter j++
            if(s[i] == sub[j] || mp[sub[j]].count(s[i])){
                j++;
                if(j==n) return true;
            }
        }

        return false;
    }
};

class Solution(object):
	def matchReplacement(self, s, sub, mappings):
		"""
		:type s: str
		:type sub: str
		:type mappings: List[List[str]]
		:rtype: bool
		"""
		n=len(s)
		m=len(sub)
		d=defaultdict(set)
		for x,y in mappings:
			d[x].add(y)
		for i in range(n-m+1):
			found=True
			for j in range(m):
				if s[i+j]!=sub[j]:
					if s[i+j] not in d[sub[j]]:
						found=False
						break
			if found:
				return True
		return False

    static boolean matchReplacement(String s, String sub, char[][] mappings) {
        
        Map<Character, Set<Character>> m = new HashMap<>();
        for(char [] c : mappings) {
            char key = c[0], value = c[1];
            Set<Character> vals = m.getOrDefault(key, new HashSet<>());
            vals.add(value);
            m.put(key, vals);
        }
        
        
        for(int i = 0; i < s.length(); i++) {
            int k = i;
            for(int j = 0; j < sub.length() && k < s.length(); j++, k++) {
                if(s.charAt(k) == sub.charAt(j)) continue;
                else if(!m.containsKey(sub.charAt(j)) || !m.get(sub.charAt(j)).contains(s.charAt(k))) break;
            }
            if(k-i == sub.length()) return true;
        }
        return false;
    }

Happy Learning – If you require any further information, feel free to contact me.