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

Thinking

Each mapping is a single replacement, so we only need to try every alignment of \(sub\) inside \(s\) and check characters one by one. \(|s| \le 5000\), so the product of alignments and substring length is about \(2.5 \times 10^7\), which is acceptable.

A character may map to several replacements; scanning the mapping list at every position repeats work. Store the reachable set of each old character in a hash table, then test “equal or replaceable” in \(O(1)\) per pair.

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

Thinking

Method 1 stores mappings in hash sets, so constants follow hashing. The alphabet is only letters and digits, so a \(128 \times 128\) boolean table records reachability and turns each query into an index lookup. The alignment order is unchanged.

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

Python3JavaC++Go

class Solution:
    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:
        d = [[False] * 128 for _ in range(128)]
        for a, b in mappings:
            d[ord(a)][ord(b)] = True
        for i in range(len(s) - len(sub) + 1):
            if all(
                a == b or d[ord(b)][ord(a)] 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) {
        boolean[][] d = new boolean[128][128];
        for (var e : mappings) {
            d[e[0]][e[1]] = true;
        }
        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[b][a]) {
                    ok = false;
                }
            }
            if (ok) {
                return true;
            }
        }
        return false;
    }
}

class Solution {
public:
    bool matchReplacement(string s, string sub, vector<vector<char>>& mappings) {
        bool d[128][128]{};
        for (auto& e : mappings) {
            d[e[0]][e[1]] = true;
        }
        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][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
}

2301. Match Substring After Replacement

Description

Solutions

Solution 1: Hash Table + Enumeration

Solution 2: Array + Enumeration

Comments