833. Find And Replace in String —— weekly contest 84
Find And Replace in String
To some string S
, we will perform some replacement operations that replace groups of letters with new ones (not necessarily the same size).
Each replacement operation has 3
parameters: a starting index i
, a source word x
and a target word y
. The rule is that if x
starts at position i
in the original string S
, then we will replace that occurrence of x
with y
. If not, we do nothing.
For example, if we have S = "abcd"
and we have some replacement operation i = 2, x = "cd", y = "ffff"
, then because "cd"
starts at position 2
in the original string S
, we will replace it with "ffff"
.
Using another example on S = "abcd"
, if we have both the replacement operation i = 0, x = "ab", y = "eee"
, as well as another replacement operation i = 2, x = "ec", y = "ffff"
, this second operation does nothing because in the original string S[2] = 'c'
, which doesn't match x[0] = 'e'
.
All these operations occur simultaneously. It's guaranteed that there won't be any overlap in replacement: for example, S = "abc", indexes = [0, 1], sources = ["ab","bc"]
is not a valid test case.
Example 1:
Input: S = "abcd", indexes = [0,2], sources = ["a","cd"], targets = ["eee","ffff"]
Output: "eeebffff"
Explanation: "a" starts at index 0 in S, so it's replaced by "eee".
"cd" starts at index 2 in S, so it's replaced by "ffff".
Example 2:
Input: S = "abcd", indexes = [0,2], sources = ["ab","ec"], targets = ["eee","ffff"]
Output: "eeecd"
Explanation: "ab" starts at index 0 in S, so it's replaced by "eee".
"ec" doesn't starts at index 2 in the original S, so we do nothing.
Notes:
0 <= indexes.length = sources.length = targets.length <= 100
0 < indexes[i] < S.length <= 1000
- All characters in given inputs are lowercase letters.
1 class Solution {
2 public:
3 string findReplaceString(string S, vector<int>& indexes, vector<string>& sources, vector<string>& targets) {
4 string res;
5 res = S;
6 map<int,int> mp; // indexes's value relate to index after sorting
7 for(int i = 0; i < indexes.size();i++){
8 mp[indexes[i]] = i;
9 }
10 vector<int> cpi = indexes;
11 sort(cpi.begin(),cpi.end()); //cpi.end() means the pos after the last number
12
13 for(int i = cpi.size()-1; i>=0 ;i--){ //from big to small
14 int n = cpi[i];
15 int m = mp[cpi[i]];
16 if(sources[m] == S.substr(n,sources[m].size())){ //substr(int pos, int len)
17 res.replace(n,sources[m].size(),targets[m]); //replace(int pos, int len, string str) or ::iterator
18 }
19 }
20 return res;
21 }
22 };
主要操作是取子串和替代的操作。
主要算法是sort和从大到小操作以避免index改变造成的不能实现同时替换的问题。
最新文章
- 新手如何在gdb中存活
- LINUX 下时间转换为秒数
- Android APK是否需要预解压
- Slick – 这是你需要的最后一款 jQuery 传送带插件
- HDU 2818 (矢量并查集)
- spring MVC项目中,欢迎页首页根路径到底是怎么设置的
- EasyHook远注简单监控示例 z
- Windows 无法启动xx服务 错误1053:服务没有及时响应启动或控制请求
- __stack_chk_fail栈检查失败
- IOS跟ANDROID的区别
- SpringBoot中使用JNnit4(入门篇)
- uwsgi+anaconda+nginx部署django项目(ubuntu下)
- [Linux]安装node.js
- requests+django+bs4实现一个web微信的功能
- 用VS制作的windows服务安装包 安装完后如何让服务自动启动
- underscore.js源码研究(3)
- C# AES 加密与解密
- app开发技术调研
- 20155307刘浩《网络对抗》逆向及Bof基础
- web 常用富文本编辑器
热门文章
- 玩转Libmodbus(二) 写代码体验
- 017 01 Android 零基础入门 01 Java基础语法 02 Java常量与变量 11 变量综合案例
- 【题解】【HAOI2011】Problem b
- 启动VNC Shell扩展
- 【总结】Oracle数据库 查看表空间和增加表空间
- background-size 详解
- Jersey实现跨服务器上传图片:UniformInterfaceException:403 Forbidden
- 多测师讲解python _练习题003_高级讲师肖sir
- 在shell中截取心仪的字符串
- Python中列表、元组、字典、集合与字符串,相关函数,持续更新中……