LeetCode 题解工作台
替换字符后匹配
给你两个字符串 s 和 sub 。同时给你一个二维字符数组 mappings ，其中 mappings[i] = [old i , new i ] 表示你可以将 sub 中任意数目的 old i 字符替换为 new i 。 sub 中每个字符 不能 被替换超过一次。 如果使用 mappings 替换…
4
题型
4
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
我们先用哈希表 记录每个字符可以替换成的字符集合。 然后我们枚举 中所有长度为 长度的子串，判断字符串 是否可以通过替换得到该子串，如果可以则返回 `true`，否则枚举下一个子串。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你两个字符串 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是大写、小写字母或者是个数字。
解题思路
方法一：哈希表 + 枚举
我们先用哈希表 记录每个字符可以替换成的字符集合。
然后我们枚举 中所有长度为 长度的子串，判断字符串 是否可以通过替换得到该子串，如果可以则返回 true，否则枚举下一个子串。
枚举结束，说明 无法通过替换得到 中的任何子串，返回 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
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on scanning all substrings of length sub.length in s and checking each character with hash lookups, giving O(s.length * sub.length) in worst-case. Space complexity is O(mappings.length) for the hash table plus O(sub.length) for tracking replacements. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate should recognize the need to scan all substrings of matching length.
- question_mark
Efficient hash-based mapping check is expected to avoid nested loops over mappings.
- question_mark
Proper handling of one-time replacement per character is crucial for correctness.
常见陷阱
外企场景- error
Replacing a character more than once violates the problem constraint and leads to false positives.
- error
Ignoring case sensitivity in s or sub can produce incorrect matches.
- error
Failing to check all substrings of s of length sub.length may miss valid matches.
进阶变体
外企场景- arrow_right_alt
Allow multiple replacements per character in sub, changing the replacement tracking logic.
- arrow_right_alt
Consider mappings that are bi-directional, requiring a different hash lookup strategy.
- arrow_right_alt
Check if sub can match s after removing certain characters instead of replacements.