算法刷题目字符串
Source
Edit
History

替换字符串中连续出现的指定字符串

替换字符串中连续出现的指定字符串

一、题目

给定三个字符串 str、from 和 to，把 str 中所有 from 的子串全部替换成 to 字符串，对连续出现 from 的部分要求只替换成一个 to 字符串，返回最终的结果字符串

举例：

1
str="abcabc123abcabc456abcabc" from="abc" to="X" 返回 "X123X456X"

二、思路

有很多思路，这里提供一种思路。先将字符串中出现 from 的地方全部赋值为 0，使用一个变量 match 为 from 的下标标识。遍历 str 字符串。同时比较 from 字符串，如果 str[i] 和 from[i] 相等，那就让 match 继续自增。直到到达 from 的最后位置，仍然相等的话，就将 str 这些位置替换为 0，长度为 from 的长度。如果在出现 str[i] 和 from[i] 不相等，那就让 match 为 0，继续遍历 str。

遍历完 str，并且替换 from 为 0 之后。此时我们就把 为 0 的区域替换为 to 字符串即可。

三、代码

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>

class Solution {
public:
    std::string replace(const std::string& str, const std::string& from, const std::string& to) {
        if (str.empty()) return "";
        std::string res(str);
        int match = 0;
        for (size_t i = 0; i < res.size(); ++i) {
            // 如果到达了最后一个位置了
            if (match == from.size()-1) {
                if (res[i] == from[match]) {
                    match = 0;
                    for (int j = i, count = from.size(); count > 0; j--, count--) {
                        res[j] = 0;
                    }
                    continue;
                }
                match = 0;
                continue;
            }
            if (res[i] == from[match]) {
                match++;
            } else {
                match = 0;
            }
        }
        std::stringstream oss;
        if (res[0] == 0) oss << to;
        auto begin = res.begin(), end = res.begin();
        bool begin_flag = false;
        for (auto iter = res.begin(); iter != res.end(); ++iter) {
            if (begin_flag == false) {
                if (*iter != 0) {
                    begin = iter;
                    begin_flag = true;
                }
                continue;
            }
            if (*iter == 0) {
                end = iter;
                oss << std::string(begin, end) << to;
                begin_flag = false;
            }
        }
        return oss.str();
    }
};

int main() {
    Solution s;
    auto res = s.replace("abcabc123abcabc456abcabc", "abc", "X");
    std::cout << res << std::endl;
    return 0;
}

时间复杂度： O(n) ，空间复杂度：O(n)