LeetCode 0833. 字符串中的查找与替换

这篇具有很好参考价值的文章主要介绍了LeetCode 0833. 字符串中的查找与替换。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【LetMeFly】833.字符串中的查找与替换

力扣题目链接:https://leetcode.cn/problems/find-and-replace-in-string/

你会得到一个字符串 s (索引从 0 开始),你必须对它执行 k 个替换操作。替换操作以三个长度均为 k 的并行数组给出:indicessources,  targets

要完成第 i 个替换操作:

  1. 检查 子字符串  sources[i] 是否出现在 原字符串 s 的索引 indices[i] 处。
  2. 如果没有出现, 什么也不做 。
  3. 如果出现,则用 targets[i] 替换 该子字符串。

例如,如果 s = "abcd" , indices[i] = 0sources[i] = "ab"targets[i] = "eee" ,那么替换的结果将是 "eeecd"

所有替换操作必须 同时 发生,这意味着替换操作不应该影响彼此的索引。测试用例保证元素间不会重叠

  • 例如,一个 s = "abc" ,  indices = [0,1]sources = ["ab","bc"] 的测试用例将不会生成,因为 "ab""bc" 替换重叠。

在对 s 执行所有替换操作后返回 结果字符串

子字符串 是字符串中连续的字符序列。

 

示例 1:

输入:s = "abcd", indexes = [0,2], sources = ["a","cd"], targets = ["eee","ffff"]
输出:"eeebffff"
解释:
"a" 从 s 中的索引 0 开始,所以它被替换为 "eee"。
"cd" 从 s 中的索引 2 开始,所以它被替换为 "ffff"。

示例 2:

输入:s = "abcd", indexes = [0,2], sources = ["ab","ec"], targets = ["eee","ffff"]
输出:"eeecd"
解释:
"ab" 从 s 中的索引 0 开始,所以它被替换为 "eee"。
"ec" 没有从原始的 S 中的索引 2 开始,所以它没有被替换。

 

提示:

  • 1 <= s.length <= 1000
  • k == indices.length == sources.length == targets.length
  • 1 <= k <= 100
  • 0 <= indexes[i] < s.length
  • 1 <= sources[i].length, targets[i].length <= 50
  • s 仅由小写英文字母组成
  • sources[i]targets[i] 仅由小写英文字母组成

方法一:模拟

首先将“替换信息”indicessourcestargets打包起来,按照indices从小到大排序,记为v

写一个函数equal(s, toCmp, start)用来判断sstart处开始是否与toCmp匹配。

这样,我们只需要用下标 i i i遍历s

  • i i i等于 v v v中待处理的 i n d i c e s indices indices,看字符串 s s s i i i处开始是否与 v v v中待处理的 s o u r c e s sources sources匹配:

    • 若匹配:进行替换(答案加上对应的 t a r g e t s targets targets i i i加上被替换掉的字符串的长度减1)
    • 否则:不进行替换(答案加上 s [ i ] s[i] s[i]
  • 否则:不进行替换(答案加上 s [ i ] s[i] s[i]

  • 时间复杂度 O ( C + n log ⁡ n ) O(C + n\log n) O(C+nlogn),其中 C C C s o u r c e s sources sources t a r g e t s targets targets中字母个数之和, n = l e n ( s o u r c e s ) n=len(sources) n=len(sources)

  • 空间复杂度 O ( C + log ⁡ n ) O(C + \log n) O(C+logn)

AC代码

C++
class Solution {
private:
    bool equal(string& s, string& toCmp, int start) {  // 返回s从下标start开始,是否与toCmp匹配
        if (start + toCmp.size() > s.size()) {
            return false;
        }
        for (int i = 0; i < toCmp.size(); i++) {
            if (s[start + i] != toCmp[i]) {
                return false;
            }
        }
        return true;
    }

public:
    string findReplaceString(string& s, vector<int>& indices, vector<string>& sources, vector<string>& targets) {
        vector<tuple<int, string, string>> v;
        for (int i = 0; i < indices.size(); i++) {
            v.push_back({indices[i], sources[i], targets[i]});
        }
        sort(v.begin(), v.end(), [](tuple<int, string, string>& a, tuple<int, string, string>& b) {
            return get<0>(a) < get<0>(b);
        });
        
        string ans;
        int nowV = 0;
        for (int i = 0; i < s.size(); i++) {
            if (nowV < v.size() && get<0>(v[nowV]) == i) {
                if (equal(s, get<1>(v[nowV]), i)) {
                    ans += get<2>(v[nowV]);
                    i += get<1>(v[nowV]).size() - 1;
                }
                else {
                    ans += s[i];
                }
                nowV++;
            }
            else {
                ans += s[i];
            }
        }
        return ans;
    }
};

同步发文于CSDN,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/132289306文章来源地址https://www.toymoban.com/news/detail-652245.html

到了这里,关于LeetCode 0833. 字符串中的查找与替换的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Windows BAT批处理字符串相关操作(字符串定义、分割、拼接、替换、切片、查找)

    使用 set 来定义字符串 代码说明: 将字符串Hello赋值给string1的变量 使用 %string1%%string2% 的方式完成字符串的拼接。 代码说明: 用来连接字符串的字符串,如果包含了特殊字符则需要使用 ^ 转义,并且需要使用 \\\"\\\" 括起来,特殊字符包括(但不限于): 符号 作用 @ 命令行回显

    2024年02月12日
    浏览(45)
  • 【C++】string字符串查找替换、比较、提取、插入和删除

    Link 加油! 感谢! 努力!

    2024年02月12日
    浏览(45)
  • LeetCode:剑指Offer 05. 替换空格 (字符串)

    🍎道阻且长,行则将至。🍓 🌻算法,不如说它是一种思考方式🍀 算法专栏: 👉🏻123 上一题:344. 反转字符串 本文速览: 🌻剑指 Offer 05 . 替换空格 - 简单 🌼151. 反转字符串中的单词-中等 题目描述 :请实现一个函数,把字符串 s 中的每个空格替换成\\\"%20\\\"。 来源:力扣(

    2023年04月11日
    浏览(90)
  • (字符串 ) 剑指 Offer 05. 替换空格 ——【Leetcode每日一题】

    难度:简单 请实现一个函数,把字符串 s 中的每个 空格 替换成 “ %20 ”。 示例 1: 输入:s = “We are happy.” 输出:“We%20are%20happy.” 限制 : 0 = s 的长度 = 10000 💡思路:双指针法 如果想把这道题目做到 极致 ,就不要只用额外的辅助空间了! 首先扩充数组到每个空格替换

    2024年02月08日
    浏览(72)
  • python/c++ Leetcode题解——2744. 最大字符串配对数目

    我们可以直接使用二重循环,枚举给定的数组 words 中的 words[i] 和 words[j] 是否可以匹配。 由于题目规定了数组 words 中包含的字符串互不相同,因此在枚举时,只要保证 ij,那么每个字符串最多匹配一次。 C++: python:

    2024年01月17日
    浏览(48)
  • Java中的字符串替换

    在Java中,String 类提供了 3 种字符串替换方法,分别是 replace()、replaceFirst() 和 replaceAll(),下面我们就来详细看一下三种的用法!     下面这套 Java300集 视频专门为零基础而制,适合准备入行Java开发的零基础,视频中穿插多个实战项目。每一个知识点都讲解的通俗易懂,由

    2024年02月11日
    浏览(48)
  • C++string类replace()函数(替换字符串中的子串)

    C++中的string类提供了replace()函数,用于替换字符串中的子串。其函数原型如下: 其中,pos表示要替换的子串在原字符串中的起始位置,len表示要替换的子串的长度,str表示用来替换的字符串。 replace()函数的使用方法非常简单,只需要传入要替换的子串的位置、长度和替换字

    2024年02月05日
    浏览(55)
  • Python 按规则解析并替换字符串中的变量及函数

    1、按照一定规则解析字符串中的函数、变量表达式,并替换这些表达式。这些函数表达式可能包含其它函数表达式,即支持函数嵌套 2、函数表达式格式: ${ __函数名称() }、${__函数名称( 函数参数 )} 3、变量表达式格式: ${ varName } 注意: 函数名称以 __ 打头 ${ 之间不能有空

    2024年02月05日
    浏览(45)
  • vue实现把字符串中的所有@内容,替换成带标签的

    前言:         目前有个需求是,要把输入框里面的@还有姓名高亮。 要求: 1、必须用 v-html ,带标签的给他渲染 2、把字符串中的@全部查找出来,替换掉,注意要过滤已经替换好的,不然就是无限循环了 实现方法:

    2024年02月11日
    浏览(38)
  • 【LeetCode题解】2645. 构造有效字符串的最少插入数(计算组数+动态规划+考虑相邻字母)+2085. 统计出现过一次的公共字符串(哈希表)+2807. 在链表中插入最大公约数

    2645. 构造有效字符串的最少插入数 方法一:计算组数 1.用count统计,能构成几组abc 2.如果当前字符大于之前字符,说明还在组内,不更新 3.如果当前字符小于等于之前字符,说明不是同一组的abc,组数更新 4.最终返回值:组数*3,再减去原本的字符数,就是要插入的次数 方法二

    2024年04月12日
    浏览(65)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包