1910. 删除一个字符串中所有出现的给定子字符串

来源第 55 场双周赛 Q2难度中等分数1460

题目描述

给你两个字符串 s 和 part ，请你对 s 反复执行以下操作直到所有子字符串 part 都被删除：

找到 s 中 最左边 的子字符串 part ，并将它从 s 中删除。

请你返回从 s 中删除所有 part 子字符串以后得到的剩余字符串。

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

示例 1：

输入：s = "daabcbaabcbc", part = "abc"
输出："dab"
解释：以下操作按顺序执行：
- s = "daabcbaabcbc" ，删除下标从 2 开始的 "abc" ，得到 s = "dabaabcbc" 。
- s = "dabaabcbc" ，删除下标从 4 开始的 "abc" ，得到 s = "dababc" 。
- s = "dababc" ，删除下标从 3 开始的 "abc" ，得到 s = "dab" 。
此时 s 中不再含有子字符串 "abc" 。

示例 2：

输入：s = "axxxxyyyyb", part = "xy"
输出："ab"
解释：以下操作按顺序执行：
- s = "axxxxyyyyb" ，删除下标从 4 开始的 "xy" ，得到 s = "axxxyyyb" 。
- s = "axxxyyyb" ，删除下标从 3 开始的 "xy" ，得到 s = "axxyyb" 。
- s = "axxyyb" ，删除下标从 2 开始的 "xy" ，得到 s = "axyb" 。
- s = "axyb" ，删除下标从 1 开始的 "xy" ，得到 s = "ab" 。
此时 s 中不再含有子字符串 "xy" 。

提示：

1 <= s.length <= 1000
1 <= part.length <= 1000
s 和 part 只包小写英文字母。

解法

方法一：暴力替换

思考

\(s\) 与 \(\textit{part}\) 长度分别不超过 \(10^3\)，反复寻找并删除一次出现的代价可接受，不必先构造自动机。

每次用库函数替换最左侧的 \(\textit{part}\)，直到不再出现。删除后可能拼出新的 \(\textit{part}\)，因此必须循环而非只扫一遍。

总长度每次至少缩短 \(|\textit{part}|\)，循环次数有上界，实现与题意一致。

我们循环判断 \(s\) 中是否存在字符串 \(part\)，是则进行一次替换，继续循环此操作，直至 \(s\) 中不存在字符串 \(part\)，返回此时的 \(s\) 作为答案字符串。

时间复杂度 \(O(n^2 + n \times m)\)，空间复杂度 \(O(n + m)\)。其中 \(n\) 和 \(m\) 分别是字符串 \(s\) 和字符串 \(part\) 的长度。

Python3JavaC++GoTypeScript

class Solution:
    def removeOccurrences(self, s: str, part: str) -> str:
        while part in s:
            s = s.replace(part, '', 1)
        return s

class Solution {
    public String removeOccurrences(String s, String part) {
        while (s.contains(part)) {
            s = s.replaceFirst(part, "");
        }
        return s;
    }
}

class Solution {
public:
    string removeOccurrences(string s, string part) {
        int m = part.size();
        while (s.find(part) != -1) {
            s = s.erase(s.find(part), m);
        }
        return s;
    }
};

func removeOccurrences(s string, part string) string {
    for strings.Contains(s, part) {
        s = strings.Replace(s, part, "", 1)
    }
    return s
}

function removeOccurrences(s: string, part: string): string {
    while (s.includes(part)) {
        s = s.replace(part, '');
    }
    return s;
}

方法二：栈

思考

方法一每删掉一次就要重新扫描整串。 \(|s|\) 每次至少减少 \(1\)，轮数可达 \(O(n)\)，总时间是 \(O(n^2)\)。

从左往右读时，当前结果里若还有 \(\textit{part}\)，最左侧的那一次一定贴在当前结果的末尾：更早的出现在读到它的时候就已经删掉了。

因此用一个栈保存还没被删掉的字符。每压入一个字符，若末尾的 \(m\) 个字符等于 \(\textit{part}\) 就弹出。一遍扫描即按题意完成所有删除。

用字符串 \(st\) 模拟栈，从左到右扫描 \(s\)。把当前字符追加到 \(st\) 末尾；若 \(st\) 的长度至少为 \(m = |\textit{part}|\)，且末尾 \(m\) 个字符恰好是 \(\textit{part}\)，则删掉这 \(m\) 个字符。扫描结束后， \(st\) 就是答案。

这样做与方法一等价：任意时刻 \(st\) 中都不含 \(\textit{part}\)，下一次能匹配上的 \(\textit{part}\) 必然以当前字符结尾，也就是剩余字符串中最左侧的一次出现。

时间复杂度 \(O(n \times m)\)，空间复杂度 \(O(n)\)。其中 \(n\) 和 \(m\) 分别是 \(s\) 和 \(\textit{part}\) 的长度。

Python3JavaC++GoTypeScript

class Solution:
    def removeOccurrences(self, s: str, part: str) -> str:
        m = len(part)
        st = []
        for c in s:
            st.append(c)
            if len(st) >= m and ''.join(st[-m:]) == part:
                del st[-m:]
        return ''.join(st)

class Solution {
    public String removeOccurrences(String s, String part) {
        int m = part.length();
        StringBuilder st = new StringBuilder();
        for (int i = 0; i < s.length(); ++i) {
            st.append(s.charAt(i));
            if (st.length() >= m && st.substring(st.length() - m).equals(part)) {
                st.setLength(st.length() - m);
            }
        }
        return st.toString();
    }
}

class Solution {
public:
    string removeOccurrences(string s, string part) {
        int m = part.size();
        string st;
        for (char c : s) {
            st.push_back(c);
            if ((int) st.size() >= m && st.compare(st.size() - m, m, part) == 0) {
                st.erase(st.size() - m);
            }
        }
        return st;
    }
};

func removeOccurrences(s string, part string) string {
    m := len(part)
    st := make([]byte, 0, len(s))
    for i := 0; i < len(s); i++ {
        st = append(st, s[i])
        if len(st) >= m && string(st[len(st)-m:]) == part {
            st = st[:len(st)-m]
        }
    }
    return string(st)
}

function removeOccurrences(s: string, part: string): string {
    const m = part.length;
    const st: string[] = [];
    for (const c of s) {
        st.push(c);
        if (st.length >= m && st.slice(-m).join('') === part) {
            st.length -= m;
        }
    }
    return st.join('');
}

1910. 删除一个字符串中所有出现的给定子字符串

题目描述

解法

方法一：暴力替换

方法二：栈

评论