LeetCode 2301. Match Substring After Replacement Solution in Java, C++, Python & Go | Explanation + Code

Description

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.

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 × n), and the space complexity is O(C²). Here, m and n are the lengths of the strings s and sub respectively, and C is the size of the character set.

PythonJavaC++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(code-box)

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; } }(code-box)

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; } };(code-box)

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 }(code-box)

Solution 2: Array + Enumeration

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

The time complexity is O(m × n), and the space complexity is O(C²).

PythonJavaC++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(code-box)

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; } }(code-box)

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; } };(code-box)

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 }(code-box)