LeetCode 6097. 替换字符后匹配（字典）

Michael阿明

发布于 2022-06-13 08:20:24

6960

发布于 2022-06-13 08:20:24

文章目录
1. 题目
2. 解题

1. 题目

给你两个字符串 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 <= 5000
0 <= mappings.length <= 1000
mappings[i].length == 2
oldi != newi
s 和 sub 只包含大写和小写英文字母和数字。
oldi 和 newi 是大写、小写字母或者是个数字。

来源：力扣（LeetCode）链接：https://leetcode.cn/problems/match-substring-after-replacement 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

把映射关系存入 dict，char -> set
滑窗遍历 s ，检查滑窗内的字符 s[i:i+len(sub)] 是否都能变成 sub

from collections import defaultdict
class Solution:
    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:
        maps = defaultdict(set)
        for m in mappings:
            maps[m[0]].add(m[1])
        for i in range(0, len(s)-len(sub)+1):
            flag = True
            for j in range(len(sub)):
                if s[i+j] == sub[j]: # 一样不需要操作
                    continue
                if s[i+j] not in maps[sub[j]]: # 不能变成 sub
                    flag = False
                    break
            if flag:
                return True
        return False

2856 ms 15.7 MB Python3

我的CSDN博客地址 https://michael.blog.csdn.net/

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-06-12，如有侵权请联系 cloudcommunity@tencent.com 删除

https