跳至主要內容

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

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

🟠   🔖  栈 字符串 模拟  🔗 力扣open in new window LeetCodeopen in new window

题目

Given two strings s and part, perform the following operation on s until all occurrences of the substring part are removed:

  • Find the leftmost occurrence of the substring part and remove it from s.

Return s after removing all occurrences of part.

A substring is a contiguous sequence of characters in a string.

Example 1:

Input: s = "daabcbaabcbc", part = "abc"

Output: "dab"

Explanation : The following operations are done:

  • s = "da** abc** baabcbc", remove "abc" starting at index 2, so s = "dabaabcbc".
  • s = "daba** abc** bc", remove "abc" starting at index 4, so s = "dababc".
  • s = "dab** abc** ", remove "abc" starting at index 3, so s = "dab".

Now s has no occurrences of "abc".

Example 2:

Input: s = "axxxxyyyyb", part = "xy"

Output: "ab"

Explanation : The following operations are done:

  • s = "axxx**xy** yyyb", remove "xy" starting at index 4 so s = "axxxyyyb".
  • s = "axx**xy** yyb", remove "xy" starting at index 3 so s = "axxyyb".
  • s = "ax**xy** yb", remove "xy" starting at index 2 so s = "axyb".
  • s = "a**xy** b", remove "xy" starting at index 1 so s = "ab".

Now s has no occurrences of "xy".

Constraints:

  • 1 <= s.length <= 1000
  • 1 <= part.length <= 1000
  • s​​​​​​ and part consists of lowercase English letters.

题目大意

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

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

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

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

示例 1：

输入： s = "daabcbaabcbc", part = "abc"

输出： "dab"

解释： 以下操作按顺序执行：

  • s = "daabc baabcbc" ，删除下标从 2 开始的 "abc" ，得到 s = "dabaabcbc" 。
  • s = "dabaabc bc" ，删除下标从 4 开始的 "abc" ，得到 s = "dababc" 。
  • s = "dababc " ，删除下标从 3 开始的 "abc" ，得到 s = "dab" 。

此时 s 中不再含有子字符串 "abc" 。

示例 2：

输入： s = "axxxxyyyyb", part = "xy"

输出： "ab"

解释： 以下操作按顺序执行：

  • s = "axxxxy yyyb" ，删除下标从 4 开始的 "xy" ，得到 s = "axxxyyyb" 。
  • s = "axxxy yyb" ，删除下标从 3 开始的 "xy" ，得到 s = "axxyyb" 。
  • s = "axxy yb" ，删除下标从 2 开始的 "xy" ，得到 s = "axyb" 。
  • s = "axy b" ，删除下标从 1 开始的 "xy" ，得到 s = "ab" 。

此时 s 中不再含有子字符串 "xy" 。

提示：

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

解题思路

我们可以利用栈来高效完成字符串匹配与移除操作：

  • 遍历字符串 s，逐字符压入栈 stack。

  • 每次压入字符后，检查栈顶是否出现了子串 part。

    • 判断当前栈长度是否大于等于 part.length，且栈顶元素与part 的最后一个字符是否相同，这样能够避免频繁构建新字符串，从而提升效率。
    • 通过 stack.slice(-n).join('') === part 判断是否匹配子串。
    • 若匹配成功，通过 stack.length -= n 将栈截断，完成子串的删除操作，避免复杂的数组切片操作。

  • 遍历结束后，将栈中的剩余元素拼接成字符串返回。

复杂度分析

  • 时间复杂度：O(m * n)，其中 m 为字符串 s 的长度，n 为子串 part 的长度。遍历一次字符串，每次匹配子串需要 O(n)。
  • 空间复杂度：O(m)，需要额外的栈空间来存储部分字符串。

代码

/**
 * @param {string} s
 * @param {string} part
 * @return {string}
 */
var removeOccurrences = function (s, part) {
	const n = part.length;
	const lastChar = part[n - 1]; // 记录 part 的最后一个字符
	let stack = []; // 用于存储字符串构建的栈

	for (let char of s) {
		stack.push(char); // 添加当前字符
		// 检查是否匹配 part
		if (
			stack.length >= n &&
			char === lastChar &&
			stack.slice(-n).join('') === part
		) {
			stack.length -= n; // 删除匹配部分
		}
	}
	return stack.join(''); // 返回最终结果
};

相关题目

题号标题题解标签难度力扣
2430对字母串可执行的最大删除数字符串 动态规划 字符串匹配 2+🔴🀄️open in new window 🔗open in new window