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) {
            al[mapping[0] - '0'].add(mapping[1]);
        }
        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) {
            d.computeIfAbsent(e[0], k -> new HashSet<>()).add(e[1]);
        }
        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:
            d[a].add(b)
        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:
            mp[b].add(a)

        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).

2301 - Match Substring After Replacement

2301. Match Substring After Replacement

Problem

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

2301. Match Substring After Replacement

Problem

Solution

All Problems

All Solutions