LeetCode 1209. 删除字符串中的所有相邻重复项 II

Categories:

题目描述
思路分析
1. 解法一：栈记录字符与计数（推荐）
相似题目

题目描述

✅ 1209. 删除字符串中的所有相邻重复项 II

思路分析

解法一：栈记录字符与计数（推荐）

核心思路：

维护栈，栈元素为 (字符, 连续次数)。

遍历字符：

若与栈顶相同，计数 +1，达到 k 则弹栈。

否则压栈新字符。

最终将栈中字符按计数展开。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串长度。

空间复杂度：O(n)。

class Solution {
    public String removeDuplicates(String s, int k) {
        char[] arr = s.toCharArray();
        char[] stack = new char[arr.length];
        int[] cnt = new int[arr.length];
        int top = -1;

        for (char c : arr) {
            if (top >= 0 && stack[top] == c) {
                cnt[top]++;
                if (cnt[top] == k) {
                    top--;
                }
            } else {
                top++;
                stack[top] = c;
                cnt[top] = 1;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i <= top; i++) {
            // 重复写入 cnt[i] 次
            for (int j = 0; j < cnt[i]; j++) {
                sb.append(stack[i]);
            }
        }
        return sb.toString();
    }
}

import "strings"

type pair1209 struct {
	ch  byte
	cnt int
}

func removeDuplicates(s string, k int) string {
	stack := make([]pair1209, 0)

	for i := 0; i < len(s); i++ {
		c := s[i]
		if len(stack) > 0 && stack[len(stack)-1].ch == c {
			stack[len(stack)-1].cnt++
			if stack[len(stack)-1].cnt == k {
				stack = stack[:len(stack)-1]
			}
		} else {
			stack = append(stack, pair1209{ch: c, cnt: 1})
		}
	}

	var sb strings.Builder
	for _, p := range stack {
		// 重复写入 p.cnt 次
		for i := 0; i < p.cnt; i++ {
			sb.WriteByte(p.ch)
		}
	}

	return sb.String()
}

相似题目

题目	难度	考察点
1047. 删除字符串中的所有相邻重复项	简单	栈
1209. 删除字符串中的所有相邻重复项 II	中等	栈
2390. 从字符串中移除星号	中等	栈
394. 字符串解码	中等	栈
71. 简化路径	中等	栈
735. 小行星碰撞	中等	栈

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/19921752