Hard

题目描述

给你两个字符串 s 和 sub。同时给你一个二维字符数组 mappings，其中 mappings[i] = [oldi, newi] 表示你可以执行以下操作任意次：

  • 将 sub 中的字符 oldi 替换为 newi。

sub 中的每个字符最多只能被替换一次。

如果通过根据 mappings 替换零个或多个字符，能够使 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 的子字符串，并且无法进行任何替换。
注意我们无法将 '0' 替换为 'o'。

示例 3：

输入：s = "Fool33tbaR", sub = "leetd", mappings = [["e","3"],["t","7"],["t","8"],["d","b"],["p","b"]]
输出：true
解释：将 sub 中的第一个和第二个 'e' 替换为 '3'，将 'd' 替换为 'b'。
现在 sub = "l33tb" 是 s 的子字符串，所以返回 true。

提示：

  • 1 <= sub.length <= s.length <= 5000
  • 0 <= mappings.length <= 1000
  • mappings[i].length == 2
  • oldi != newi
  • s 和 sub 由大写、小写英文字母和数字组成
  • oldi 和 newi 都是大写或小写英文字母或数字

解题思路

这是一个字符串匹配问题，需要考虑字符替换规则。解题的核心思路是遍历所有可能的匹配位置，然后检查每个位置是否能通过替换使 sub 匹配。

方法一：哈希表预处理 + 暴力匹配（推荐）

  1. 首先将所有映射关系存储在哈希表中，便于快速查找某个字符是否可以替换为目标字符
  2. 遍历字符串 s 中所有长度为 sub.length 的子串
  3. 对于每个子串，逐字符比较：
    • 如果字符相同，则继续
    • 如果不同，检查是否存在 sub[j] -> s[i+j] 的映射关系
    • 如果都不满足，则当前位置匹配失败

方法二：动态规划优化 可以用动态规划的思想，记录每个位置的匹配状态，但在这个问题的约束下，暴力方法已经足够高效。

时间复杂度分析：由于字符串长度最大为5000，暴力匹配的复杂度是可以接受的。哈希表的使用可以将单次字符检查的时间复杂度降到O(1)。

代码实现

class Solution {
public:
    bool matchReplacement(string s, string sub, vector<vector<char>>& mappings) {
        unordered_set<string> mapping_set;
        for (const auto& mapping : mappings) {
            mapping_set.insert(string(1, mapping[0]) + string(1, mapping[1]));
        }
        
        int n = s.length(), m = sub.length();
        for (int i = 0; i <= n - m; i++) {
            bool match = true;
            for (int j = 0; j < m; j++) {
                char s_char = s[i + j];
                char sub_char = sub[j];
                if (s_char == sub_char) {
                    continue;
                }
                string key = string(1, sub_char) + string(1, s_char);
                if (mapping_set.find(key) == mapping_set.end()) {
                    match = false;
                    break;
                }
            }
            if (match) {
                return true;
            }
        }
        return false;
    }
};

class Solution:
    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:
        mapping_set = set()
        for old, new in mappings:
            mapping_set.add((old, new))
        
        n, m = len(s), len(sub)
        for i in range(n - m + 1):
            match = True
            for j in range(m):
                s_char = s[i + j]
                sub_char = sub[j]
                if s_char == sub_char:
                    continue
                if (sub_char, s_char) not in mapping_set:
                    match = False
                    break
            if match:
                return True
        return False

public class Solution {
    public bool MatchReplacement(string s, string sub, char[][] mappings) {
        HashSet<string> mappingSet = new HashSet<string>();
        foreach (var mapping in mappings) {
            mappingSet.Add(mapping[0].ToString() + mapping[1].ToString());
        }
        
        int n = s.Length, m = sub.Length;
        for (int i = 0; i <= n - m; i++) {
            bool match = true;
            for (int j = 0; j < m; j++) {
                char sChar = s[i + j];
                char subChar = sub[j];
                if (sChar == subChar) {
                    continue;
                }
                string key = subChar.ToString() + sChar.ToString();
                if (!mappingSet.Contains(key)) {
                    match = false;
                    break;
                }
            }
            if (match) {
                return true;
            }
        }
        return false;
    }
}

/**
 * @param {string} s
 * @param {string} sub
 * @param {character[][]} mappings
 * @return {boolean}
 */
var matchReplacement = function(s, sub, mappings) {
    const canReplace = new Map();
    
    for (let [old, newChar] of mappings) {
        if (!canReplace.has(old)) {
            canReplace.set(old, new Set());
        }
        canReplace.get(old).add(newChar);
    }
    
    for (let i = 0; i <= s.length - sub.length; i++) {
        let match = true;
        for (let j = 0; j < sub.length; j++) {
            const sChar = s[i + j];
            const subChar = sub[j];
            
            if (sChar === subChar) {
                continue;
            }
            
            if (canReplace.has(subChar) && canReplace.get(subChar).has(sChar)) {
                continue;
            }
            
            match = false;
            break;
        }
        
        if (match) {
            return true;
        }
    }
    
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n × m + k)，其中 n 是字符串 s 的长度，m 是字符串 sub 的长度，k 是映射数组的长度
空间复杂度O(k)，用于存储映射关系的哈希集合

相关题目