Skip to content

Latest commit

 

History

History
206 lines (164 loc) · 6.85 KB

README.md

File metadata and controls

206 lines (164 loc) · 6.85 KB

833. 字符串中的查找与替换

English Version

题目描述

你会得到一个字符串 s (索引从 0 开始)，你必须对它执行 k 个替换操作。替换操作以三个长度均为 k 的并行数组给出：indices, sources,  targets。

要完成第 i 个替换操作:

  1. 检查 子字符串  sources[i] 是否出现在 原字符串 s 的索引 indices[i] 处。
  2. 如果没有出现， 什么也不做 。
  3. 如果出现，则用 targets[i] 替换 该子字符串。

例如，如果 s = "abcd" ， indices[i] = 0 , sources[i] = "ab"， targets[i] = "eee" ，那么替换的结果将是 "eeecd" 。

所有替换操作必须 同时 发生，这意味着替换操作不应该影响彼此的索引。测试用例保证元素间不会重叠 。

  • 例如，一个 s = "abc" ，  indices = [0,1] ， sources = ["ab"，"bc"] 的测试用例将不会生成，因为 "ab" 和 "bc" 替换重叠。

在对 s 执行所有替换操作后返回 结果字符串 。

子字符串 是字符串中连续的字符序列。

 

示例 1：

输入：s = "abcd", indexes = [0,2], sources = ["a","cd"], targets = ["eee","ffff"]
输出："eeebffff"
解释：
"a" 从 s 中的索引 0 开始，所以它被替换为 "eee"。
"cd" 从 s 中的索引 2 开始，所以它被替换为 "ffff"。

示例 2：

输入：s = "abcd", indexes = [0,2], sources = ["ab","ec"], targets = ["eee","ffff"]
输出："eeecd"
解释：
"ab" 从 s 中的索引 0 开始，所以它被替换为 "eee"。
"ec" 没有从原始的 S 中的索引 2 开始，所以它没有被替换。

 

提示：

  • 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 仅由小写英文字母组成
  • sources[i] 和 targets[i] 仅由小写英文字母组成

解法

方法一：模拟

我们先遍历 indices，对于每个 $i$，如果 s[indices[i]: indices[i] + len(sources[i])] == sources[i]，则说明 $s$ 中从 indices[i] 开始的 len(sources[i]) 个字符与 sources[i] 相等，我们记录下标 indices[i] 处需要替换的是 targets[i]，否则不需要替换。

然后我们从左到右遍历 $s$，如果当前下标 $i$ 处需要替换，则将 targets[d[i]] 加入答案，并且 $i$ 跳过 len(sources[d[i]]) 个字符，否则将 s[i] 加入答案，然后 $i$ 自增 $1$。

时间复杂度 $O(k + n)$，空间复杂度 $O(n)$。其中 $k$ 和 $n$ 分别是 indices 和 $s$ 的长度。

Python3

class Solution:
    def findReplaceString(self, s: str, indices: List[int], sources: List[str], targets: List[str]) -> str:
        n = len(s)
        d = [-1] * n
        for i, (j, source) in enumerate(zip(indices, sources)):
            if s[j: j + len(source)] == source:
                d[j] = i
        ans = []
        i = 0
        while i < n:
            if d[i] >= 0:
                ans.append(targets[d[i]])
                i += len(sources[d[i]])
            else:
                ans.append(s[i])
                i += 1
        return ''.join(ans)

Java

class Solution {
    public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {
        int n = s.length();
        int[] d = new int[n];
        Arrays.fill(d, -1);
        for (int i = 0; i < indices.length; ++i) {
            int j = indices[i];
            String source = sources[i];
            if (s.substring(j, Math.min(n, j + source.length())).equals(source)) {
                d[j] = i;
            }
        }
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < n;) {
            if (d[i] >= 0) {
                ans.append(targets[d[i]]);
                i += sources[d[i]].length();
            } else {
                ans.append(s.charAt(i++));
            }
        }
        return ans.toString();
    }
}

C++

class Solution {
public:
    string findReplaceString(string s, vector<int>& indices, vector<string>& sources, vector<string>& targets) {
        int n = s.size();
        vector<int> d(n, -1);
        for (int i = 0; i < indices.size(); ++i) {
            int j = indices[i];
            string source = sources[i];
            if (s.substr(j, source.size()) == source) {
                d[j] = i;
            }
        }
        string ans;
        for (int i = 0; i < n;) {
            if (d[i] >= 0) {
                ans += targets[d[i]];
                i += sources[d[i]].size();
            } else {
                ans += s[i++];
            }
        }
        return ans;
    }
};

Go

func findReplaceString(s string, indices []int, sources []string, targets []string) string {
	n := len(s)
	d := make([]int, n)
	for i, j := range indices {
		source := sources[i]
		if s[j:min(j+len(source), n)] == source {
			d[j] = i + 1
		}
	}
	ans := &strings.Builder{}
	for i := 0; i < n; {
		if d[i] > 0 {
			ans.WriteString(targets[d[i]-1])
			i += len(sources[d[i]-1])
		} else {
			ans.WriteByte(s[i])
			i++
		}
	}
	return ans.String()
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

...