Welcome to Subscribe On Youtube
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
ofsub
withnewi
.
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
andsub
consist of uppercase and lowercase English letters and digits. -
oldi
andnewi
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).