2301. Match Substring After Replacement

Description

You are given two strings s and sub. You are also given a 2D character array mappings where mappings[i] = [old_i, new_i] indicates that you may perform the following operation any number of times:

Replace a character old_i of sub with new_i.

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
old_i != new_i
s and sub consist of uppercase and lowercase English letters and digits.
old_i and new_i are either uppercase or lowercase English letters or digits.

Solutions

Solution 1: Hash Table + Enumeration

First, we use a hash table \(d\) to record the set of characters that each character can be replaced with.

Then we enumerate all substrings of length \(sub\) in \(s\), and judge whether the string \(sub\) can be obtained by replacement. If it can, return true, otherwise enumerate the next substring.

At the end of the enumeration, it means that \(sub\) cannot be obtained by replacing any substring in \(s\), so return false.

The time complexity is \(O(m \times n)\), and the space complexity is \(O(C^2)\). Here, \(m\) and \(n\) are the lengths of the strings \(s\) and \(sub\) respectively, and \(C\) is the size of the character set.

Python3JavaC++Go

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

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 {
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 := map[byte]map[byte]bool{}
    for _, e := range mappings {
        if d[e[0]] == nil {
            d[e[0]] = map[byte]bool{}
        }
        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
}

Solution 2: Array + Enumeration

Since the character set only contains uppercase and lowercase English letters and numbers, we can directly use a \(128 \times 128\) array \(d\) to record the set of characters that each character can be replaced with.

The time complexity is \(O(m \times n)\), and the space complexity is \(O(C^2)\).