class Solution {
public:
bool matchReplacement(string s, string sub, vector<vector<char>>& mappings) {
}
};
2301. 替换字符后匹配
给你两个字符串 s 和 sub 。同时给你一个二维字符数组 mappings ，其中 mappings[i] = [oldi, newi] 表示你可以将 sub 中任意数目的 oldi 字符替换为 newi 。sub 中每个字符 不能 被替换超过一次。
如果使用 mappings 替换 0 个或者若干个字符，可以将 sub 变成 s 的一个子字符串，请你返回 true，否则返回 false 。
一个 子字符串 是字符串中连续非空的字符序列。
示例 1：
输入：s = "fool3e7bar", sub = "leet", mappings = [["e","3"],["t","7"],["t","8"]] 输出：true 解释：将 sub 中第一个 'e' 用 '3' 替换，将 't' 用 '7' 替换。 现在 sub = "l3e7" ，它是 s 的子字符串，所以我们返回 true 。
示例 2：
输入：s = "fooleetbar", sub = "f00l", mappings = [["o","0"]] 输出：false 解释：字符串 "f00l" 不是 s 的子串且没有可以进行的修改。 注意我们不能用 'o' 替换 '0' 。
示例 3：
输入：s = "Fool33tbaR", sub = "leetd", mappings = [["e","3"],["t","7"],["t","8"],["d","b"],["p","b"]] 输出：true 解释：将 sub 里第一个和第二个 'e' 用 '3' 替换，用 'b' 替换 sub 里的 'd' 。 得到 sub = "l33tb" ，它是 s 的子字符串，所以我们返回 true 。
提示：
1 <= sub.length <= s.length <= 50000 <= mappings.length <= 1000mappings[i].length == 2oldi != newis 和 sub 只包含大写和小写英文字母和数字。oldi 和 newi 是大写、小写字母或者是个数字。原站题解
python3 解法, 执行用时: 1476 ms, 内存消耗: 31.2 MB, 提交时间: 2023-06-13 14:32:58
class Solution:
def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:
d = {}
for k,v in mappings:
d[k] = d.get(k, k) + v
return bool(re.search("".join(f"[{d.get(c, c)}]" for c in sub), s))
golang 解法, 执行用时: 36 ms, 内存消耗: 4.9 MB, 提交时间: 2023-06-13 14:32:37
func matchReplacement(s, sub string, mappings [][]byte) bool {
mp := ['z' + 1]['z' + 1]bool{}
for _, p := range mappings {
mp[p[0]][p[1]] = true
}
next:
for i := len(sub); i <= len(s); i++ {
for j, c := range s[i-len(sub) : i] {
if byte(c) != sub[j] && !mp[sub[j]][c] {
continue next
}
}
return true
}
return false
}
python3 解法, 执行用时: 2508 ms, 内存消耗: 16.6 MB, 提交时间: 2023-06-13 14:32:18
# 预处理 + 暴力枚举
class Solution:
def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:
mp = set((x, y) for x, y in mappings)
for i in range(len(sub), len(s) + 1):
if all(x == y or (x, y) in mp for x, y in zip(sub, s[i - len(sub): i])):
return True
return False