美文网首页Leetcode
Leetcode 833. Find And Replace i

Leetcode 833. Find And Replace i

作者: SnailTyan | 来源:发表于2021-08-12 09:38 被阅读0次

文章作者:Tyan
博客:noahsnail.com  |  CSDN  |  简书

1. Description

Find And Replace in String

2. 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

Reference

  1. https://leetcode.com/problems/find-and-replace-in-string/

相关文章

网友评论

    本文标题:Leetcode 833. Find And Replace i

    本文链接:https://www.haomeiwen.com/subject/mtvjmltx.html