替换字符后匹配

标签: 数组 哈希表 字符串 字符串匹配

难度: Hard

给你两个字符串 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 是大写、小写字母或者是个数字。

Submission

运行时间: 67 ms

内存: 16.8 MB

class Solution:
    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:
        old = [0]*128
        new = [0]*128
        for i, c in enumerate(s):
            new[ord(c)] |= 1 << i
        
        old = new[:]
        for c1, c2 in mappings:
            old[ord(c1)] |= new[ord(c2)]
        ans = old[ord(sub[0])]
        for i, c in enumerate(sub):
            ans &= old[ord(c)] >> i
        return ans > 0

Explain

该题解使用了位运算和位掩码的方法来检查是否可以通过替换使得子字符串 `sub` 匹配字符串 `s` 的某一部分。首先，使用两个大小为128的数组（因为ASCII字符的范围是0-127），`old` 和 `new` 来表示字符在字符串 `s` 中出现的位置。`new` 数组通过位移和按位或操作记录每个字符在 `s` 中的位置。然后，使用 `mappings` 更新 `old` 数组，使得如果字符 `c1` 可以被映射为 `c2`，则 `c1` 的位置信息也会包含 `c2` 的位置信息。最后，通过按位与操作检查 `sub` 是否为 `s` 的子字符串。如果 `sub` 中的每个字符都可以在 `s` 中找到对应位置，且这些位置是连续的，则返回 `true`。

时间复杂度: O(n + m + k)

空间复杂度: O(1)

class Solution:
    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:
        old = [0]*128
        new = [0]*128
        for i, c in enumerate(s):
            new[ord(c)] |= 1 << i # 使用位运算记录字符c在s中的每个位置
        
        old = new[:] # 复制new到old
        for c1, c2 in mappings:
            old[ord(c1)] |= new[ord(c2)] # 根据mappings更新old数组
        ans = old[ord(sub[0])] # 初始化ans为sub的第一个字符可能的位置
        for i, c in enumerate(sub):
            ans &= old[ord(c)] >> i # 检查sub中的每个字符是否可以连续匹配
        return ans > 0

Explore

在题解中，位运算用于高效地记录和查询每个字符在字符串`s`中的所有位置。具体来说，使用一个长度为128的数组`new`，每个位置对应ASCII表中一个字符。对于字符串`s`中的每个字符，使用`ord(c)`得到该字符的ASCII码作为数组索引。然后，将整数1左移`i`位，其中`i`是字符在字符串`s`中的索引位置，通过按位或操作`|=`，将这个位标记到`new[ord(c)]`中。这样，`new[ord(c)]`的每个位代表字符`c`在字符串`s`中的具体位置（如果某位是1，表示该字符出现在对应的位置上）。

题解中选用128大小的数组是因为ASCII字符集包含128个字符，从0到127。使用固定大小的数组可以直接通过字符的ASCII码快速访问，操作简单且效率高。相比之下，使用哈希表虽然在处理非ASCII字符集时更为灵活，但对于ASCII字符，哈希表的额外空间和时间开销（处理哈希冲突和动态扩容）在本题中是不必要的，因此选择数组可以提供更优的性能。

题解中的操作`old[ord(c1)] |= new[ord(c2)]`是将字符`c2`在字符串`s`中的所有位置信息添加到字符`c1`的位置信息中。这样的映射更新确保如果`mappings`中指定`c1`可以被替换为`c2`，那么在尝试匹配子字符串`sub`时，`c1`的位置也会考虑`c2`的所有可能位置。这意味着，在检查`sub`是否为`s`的子字符串时，即使某个位置原本是由`c2`占据，只要`mappings`允许将`c2`替换为`c1`，这个位置也可以被视为有效的`c1`位置。因此，这种更新方式支持了字符的灵活替换和匹配。