题目地址：https://leetcode.com/problems/find-and-replace-in-string/description/
题目描述：
Tosome 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.
Forexample, 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'.
Allthese 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.
题目大意
给了原始的字符串S，给出了要开始替换的位置indexes，判断S在indexes的位置向后是否能匹配sources中对应位置的元素，如果相等，则把S的该部分替换成targets对应的部分。
解题方法
不可能直接对S进行替换操作的，因为那样直接改变了S的值和长度，影响以后的匹配操作。
刚开始时想直接遍历indexes的方式去替换，以为这样可以不用对S遍历，节省了时间。事实上这个思路是错的，注意到题目给出的indexes的元素格式和S的长度范围是相等的，因此没有降低时间复杂度。
正确的方式是对S进行遍历，因为S的长度最多也就1000，O(n)的时间复杂度完全够用。
我们在遍历的过程中，来查找每个位置的下标是否在indexes中，如果在的话，需要替换操作；否则不用。
替换操作是对S进行和sources中对应子串长度相等的切片，如果两者相等，那么需要在结果字符串中加入targets对应元素；不等，那还是使用source的切片。
代码如下：
class Solution(object):
def findReplaceString(self, S, indexes, sources, targets):
"""
:type S: str
:type indexes: List[int]
:type sources: List[str]
:type targets: List[str]
:rtype: str
"""
ans = ""
i = 0
while i < len(S):
if i not in indexes:
ans += S[i]
i += 1
else:
ind = indexes.index(i)
source = sources[ind]
target = targets[ind]
part = S[i : i + len(source)]
if part == source:
ans += target
else:
ans += part
i += len(source)
return ans
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发