[LeetCode] 833. Find And Replace in String_Medium tag: array

本文主要是介绍[LeetCode] 833. Find And Replace in String_Medium tag: array，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Y

ou are given a 0-indexed string s that you must perform k replacement operations on. The replacement operations are given as three 0-indexed parallel arrays, indices, sources, and targets, all of length k.

To complete the ith replacement operation:

1. Check if the substring sources[i] occurs at index indices[i] in the original string s.
2. If it does not occur, do nothing.
3. Otherwise if it does occur, replace that substring with targets[i].

For example, if s = "abcd", indices[i] = 0, sources[i] = "ab", and targets[i] = "eee", then the result of this replacement will be "eeecd".

All replacement operations must occur simultaneously, meaning the replacement operations should not affect the indexing of each other. The testcases will be generated such that the replacements will not overlap.

• For example, a testcase with s = "abc", indices = [0, 1], and sources = ["ab","bc"] will not be generated because the "ab" and "bc" replacements overlap.

Return the resulting string after performing all replacement operations on s.

A substring is a contiguous sequence of characters in a string.

Example 1:

Input: s = "abcd", indices = [0, 2], sources = ["a", "cd"], targets = ["eee", "ffff"]
Output: "eeebffff"
Explanation:
"a" occurs at index 0 in s, so we replace it with "eee".
"cd" occurs at index 2 in s, so we replace it with "ffff".

Example 2:

Input: s = "abcd", indices = [0, 2], sources = ["ab","ec"], targets = ["eee","ffff"]
Output: "eeecd"
Explanation:
"ab" occurs at index 0 in s, so we replace it with "eee".
"ec" does not occur at index 2 in s, so we do nothing.

Constraints:

• 1 <= s.length <= 1000
• k == indices.length == sources.length == targets.length
• 1 <= k <= 100
• 0 <= indexes[i] < s.length
• 1 <= sources[i].length, targets[i].length <= 50
• s consists of only lowercase English letters.
• sources[i] and targets[i] consist of only lowercase English letters.

Ideas:

因为题目已经明确说不会有overlap

1. 利用zip(indices, sources, targets) 去得到(indice, source, target)这样为tuple的array, 再存到一个dictionary里面, key = indice, value = (source, target)

2. 指针i, 如果不在lookup里面加到ans, 往下移; 如果在lookup里面并且source start with s[i:], ans += target;   Note: s.startswith(t), 都是lower case 并且有s

Code:

class Solution:
    def findReplaceString(self, s: str, indices: List[int], sources: List[str], targets: List[str]) -> str:
        lookup = {i: (src, targ) for i, src, targ in zip(indices, sources, targets)}
        i, ans = 0, ""
        while i < len(s):
            if i in lookup and s[i:].startswith(lookup[i][0]):
                    ans += lookup[i][1]
                    i += len(lookup[i][0])
            else:
                ans += s[i]
                i += 1
        return ans

这篇关于[LeetCode] 833. Find And Replace in String_Medium tag: array的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！