【LeetCode】833. Find And Replace in String 解题报告（Python）

标签（空格分隔）： LeetCode

作者： 负雪明烛 id： fuxuemingzhu 个人博客： http://fuxuemingzhu.cn/

---

题目地址：https://leetcode.com/problems/find-and-replace-in-string/description/

题目描述：

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.

题目大意

给了原始的字符串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

日期

2018 年 7 月 18 日 ———— 现在需要的还是夯实基础，算法和理论