Medium

题目描述

给你两个字符串 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 = "ababcc" 和 pattern = "abc"。
  • 你可以维护一个字符栈，如果栈顶的 pattern 长度的字符与 pattern 匹配，则删除它们。

解题思路

这道题要求反复删除字符串中的指定子串，直到不再包含该子串为止。关键在于删除操作可能会产生新的匹配模式。

思路分析：

我们可以使用栈（或字符串）来模拟这个过程。核心思想是逐个字符地构建结果，每当栈顶形成了目标子串时就立即删除。

具体步骤：

  1. 遍历字符串 s 的每个字符，将其加入栈（结果字符串）
  2. 每次添加字符后，检查栈顶是否形成了长度为 part.length() 的子串，且该子串等于 part
  3. 如果匹配，则从栈顶删除对应长度的字符
  4. 继续处理下一个字符，直到遍历完成

这种方法的优势在于：

  • 能够及时发现并删除新形成的模式
  • 时间复杂度相对较好，避免了重复扫描
  • 实现相对简单

另一种直观的方法是使用字符串的 find 和 erase 方法反复查找删除，但效率较低，在最坏情况下时间复杂度可能达到 O(n²)。

推荐解法： 栈模拟法，时间和空间效率都比较好。

代码实现

class Solution {
public:
    string removeOccurrences(string s, string part) {
        string result;
        int partLen = part.length();
        
        for (char c : s) {
            result.push_back(c);
            
            if (result.length() >= partLen && 
                result.substr(result.length() - partLen) == part) {
                result.erase(result.length() - partLen);
            }
        }
        
        return result;
    }
};

class Solution:
    def removeOccurrences(self, s: str, part: str) -> str:
        stack = []
        part_len = len(part)
        
        for char in s:
            stack.append(char)
            
            if len(stack) >= part_len and ''.join(stack[-part_len:]) == part:
                for _ in range(part_len):
                    stack.pop()
        
        return ''.join(stack)

public class Solution {
    public string RemoveOccurrences(string s, string part) {
        StringBuilder result = new StringBuilder();
        int partLen = part.Length;
        
        foreach (char c in s) {
            result.Append(c);
            
            if (result.Length >= partLen) {
                string lastPart = result.ToString(result.Length - partLen, partLen);
                if (lastPart == part) {
                    result.Remove(result.Length - partLen, partLen);
                }
            }
        }
        
        return result.ToString();
    }
}

var removeOccurrences = function(s, part) {
    while (s.includes(part)) {
        s = s.replace(part, '');
    }
    return s;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n × m)n 为字符串 s 的长度，m 为 part 的长度。每个字符最多被处理常数次，每次比较需要 O(m) 时间
空间复杂度O(n)需要额外的栈或字符串来存储结果，最坏情况下存储整个原字符串

相关题目