视频直播网站建设方案,办网络宽带多少钱,白城哪家做网站,宜春做网站的联系电话本文属于「征服LeetCode」系列文章之一#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁#xff0c;本系列将至少持续到刷完所有无锁题之日为止#xff1b;由于LeetCode还在不断地创建新题#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章… 本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。 为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。 由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。 你会得到一个字符串 s (索引从 0 开始)你必须对它执行 k 个替换操作。替换操作以三个长度均为 k 的并行数组给出indices, sources, targets。
要完成第 i 个替换操作:
检查 子字符串 sources[i] 是否出现在 原字符串 s 的索引 indices[i] 处。如果没有出现 什么也不做 。如果出现则用 targets[i] 替换 该子字符串。
例如如果 s abcd indices[i] 0 , sources[i] ab targets[i] eee 那么替换的结果将是 eeecd 。
所有替换操作必须 同时 发生这意味着替换操作不应该影响彼此的索引。测试用例保证元素间不会重叠 。
例如一个 s abc indices [0,1] sources [abbc] 的测试用例将不会生成因为 ab 和 bc 替换重叠。
在对 s 执行所有替换操作后返回 结果字符串 。
子字符串 是字符串中连续的字符序列。
示例 1
输入s abcd, indices [0,2], sources [a,cd], targets [eee,ffff]
输出eeebffff
解释
a 从 s 中的索引 0 开始所以它被替换为 eee。
cd 从 s 中的索引 2 开始所以它被替换为 ffff。示例 2
输入s abcd, indices [0,2], sources [ab,ec], targets [eee,ffff]
输出eeecd
解释
ab 从 s 中的索引 0 开始所以它被替换为 eee。
ec 没有从原始的 S 中的索引 2 开始所以它没有被替换。提示
1 s.length 1000k indices.length sources.length targets.length1 k 1000 indices[i] s.length1 sources[i].length, targets[i].length 50s 仅由小写英文字母组成sources[i] 和 targets[i] 仅由小写英文字母组成 解法 字符串哈希表模拟
设 s s s 长度为 n n n 创建一个长为 n n n 的 m a t c h I n d e x matchIndex matchIndex 列表初始化每个元素为 − 1 -1 −1 。
遍历每个替换操作。对于第 i i i 个替换操作如果从 indices [ i ] \textit{indices}[i] indices[i] 开始的字符串有前缀 sources [ i ] \textit{sources}[i] sources[i] 则可以替换成 target [ i ] \textit{target}[i] target[i] 。例如 sabcd s[1:]bcd 有前缀 bc 。此时记录 m a t c h I n d e x [ i n d i c e s [ i ] ] i matchIndex[indices[i]]i matchIndex[indices[i]]i 后面的 i i i 指的是 t a r g e t [ i ] target[i] target[i] 表示「从原串的 i n d i c e s [ i ] indices[i] indices[i] 位置开始要进行替换替换后从 s o u r c e s [ i ] sources[i] sources[i] 变为 t a r g e t s [ i ] targets[i] targets[i] 」。
然后遍历 m a t c h I n d e x matchIndex matchIndex 列表如果 m a t c h I n d e x [ i ] ≠ − 1 matchIndex[i] \ne -1 matchIndex[i]−1 说明要进行替换把 t a r g e t s [ m a t c h I n d e x [ i ] ] targets[matchIndex[i]] targets[matchIndex[i]] 加入答案然后 i i i 增加 s o u r c e s [ m a t c h I n d e x [ i ] ] sources[matchIndex[i]] sources[matchIndex[i]] 的长度否则说明无需替换把 s [ i ] s[i] s[i] 加入答案然后 i i i 加一。
class Solution {
public:string findReplaceString(string s, vectorint indices, vectorstring sources, vectorstring targets) {string ans;int k indices.size(), n s.size();int matchIndex[n];memset(matchIndex, -1, sizeof(matchIndex));for (int i 0; i k; i) {int sn sources[i].size();bool isMatch true;for (int j indices[i]; j indices[i] sn; j) { // j为原串中的下标if (sources[i][j - indices[i]] ! s[j]) { // 某个字符不同isMatch false;break;}} // 如果子串出现在原串的indices[i]处则记录要用来替换的新串的下标if (isMatch) matchIndex[indices[i]] i;}for (int i 0; i n; i) {if (matchIndex[i] ! -1) { // 要进行替换int index matchIndex[i];ans targets[index];i indices[index] sources[index].size() - 1; // i要跳转到原串后面} else ans.push_back(s[i]);}return ans;}
};复杂度分析
时间复杂度 O ( M N ) O(MN) O(MN)空间复杂度 O ( M N ) O(MN) O(MN)
