Luobuyu's Blog

0%

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

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 2.7k 阅读时长 ≈ 2 分钟
从后往前会比较简单。

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

题目描述：

你会得到一个字符串 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\le s.len \le 1000;1\le k \le 100$

题解：

从前往后替换的话，由于前面的被替换掉，影响了当前字符串的长度，需要换算到被替换后的下标。

从后往前的话，不会影响到前面替换的下标，会更加简单。

也可以使用一个数组，表示当前位置是否被替换，如果被替换的话就加上 $target[i]$ ，然后跳过 $len=source[i]$ 长度；否则的话就直接加上 $s[i]$ 。

代码：

从前往后

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
class Solution {
public:
    string findReplaceString(string s, vector<int>& indices, vector<string>& sources, vector<string>& targets) {
        int n = indices.size();
        vector<int> idx(n);
        iota(idx.begin(), idx.end(), 0);    
        sort(idx.begin(), idx.end(), [&](int i, int j) {
            return indices[i] < indices[j];
        });
        string ans = "";
        int k = 0;
        for (int i = 0; i < n; i++) {
            int j = indices[idx[i]];
            while (k < j) {
                ans += s[k++];
            }
            if (s.substr(j, sources[idx[i]].size()) == sources[idx[i]]) {
                ans += targets[idx[i]];
                 k += sources[idx[i]].size();
            }
        }
        ans += s.substr(k);
        return ans;
    }
};

从后往前

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    string findReplaceString(string s, vector<int>& indices, vector<string>& sources, vector<string>& targets) {
        int n = indices.size();
        vector<int> idx(n);
        for (int i = 0; i < n; ++i) idx[i] = i;
        sort(idx.begin(), idx.end(), [&](int i, int j) {
            return indices[i] > indices[j];
        });

        for (int i: idx) {
            int st = indices[i];
            int len = sources[i].size();
            if (memcmp(s.c_str() + st, sources[i].c_str(), len) == 0) {
                s.replace(st, len, targets[i]);
            }
        }
        return s;
    }
};
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    string findReplaceString(string s, vector<int> &indices, vector<string> &sources, vector<string> &targets)
    {
        int n = s.length(), k = indices.size();
        vector<int> replace(n, -1);
        for (int i = 0; i < k; ++i)
        {
            if (sources[i] == s.substr(indices[i], sources[i].length()))
            {
                replace[indices[i]] = i;
            }
        }
        string ans;
        for (int i = 0; i < n;)
        {
            if (replace[i] != -1)
            {
                ans += targets[replace[i]];
                i += sources[replace[i]].length();
            }
            else
            {
                ans += s[i];
                i++;
            }
        }
        return ans;
    }
};