文章作者:Tyan
博客:noahsnail.com | CSDN | 简书
1. Description
Find And Replace in String2. Solution
解析:Version 1,先排序,根据索引排序,对源字符串和目标字符串也根据索引的排序顺序排序,这样做主要为了判断是否有重叠字符串。遍历所有索引,如果当前索引加上源字符串的长度与下一个索引重叠,则当前索引以及下一个索引对应的字符串都不能替换。如果字符串s
根据索引对应的字串与源字符串相等,则替换对应的子串,由于需要同时替换,因此s
保持不变,使用result
保存替换的结果,对于不进行替换的部分,根据位置保留到result
中。
- Version 1
class Solution:
def findReplaceString(self, s: str, indices: List[int], sources: List[str], targets: List[str]) -> str:
k = len(indices)
order = sorted(range(k), key=lambda x: indices[x])
indices = [indices[i] for i in order]
sources = [sources[i] for i in order]
targets = [targets[i] for i in order]
result = ''
i = 0
start = 0
while i < k:
index = indices[i]
source = sources[i]
target = targets[i]
if i + 1 < k and index + len(source) - 1 >= indices[i+1]:
i += 2
continue
n = len(source)
if s[index:index+n] == source:
result += s[start:index]
result += target
start = index + n
i += 1
result += s[start:]
return result
- Version 2
class Solution:
def findReplaceString(self, s: str, indices: List[int], sources: List[str], targets: List[str]) -> str:
k = len(indices)
data = sorted(zip(indices, sources, targets), key=lambda x: x[0])
result = ''
i = 0
start = 0
while i < k:
index, source, target = data[i]
n = len(source)
if i + 1 < k and index + n - 1 >= data[i+1][0]:
i += 2
continue
if s[index:index+n] == source:
result += s[start:index]
result += target
start = index + n
i += 1
result += s[start:]
return result
网友评论