题目地址: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 弟弟快看-教程,程序员编程资料站,版权归原作者所有

本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发