LeetCode 1003. 检查替换后的词是否有效

Categories:

题目描述
思路分析
1. 解法一：栈模拟消除（推荐）
相似题目

题目描述

✅ 1003. 检查替换后的词是否有效

思路分析

解法一：栈模拟消除（推荐）

核心思路：

逐字符入栈，当栈顶连续三个字符为 “a”、”b”、”c” 时弹出。

所有替换都等价于不断消除 “abc” 子串，最终栈空则有效。

每个字符最多入栈出栈一次，整体线性。

复杂度分析：

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

空间复杂度：O(n)，栈的额外空间。

import java.util.*;

class Solution {
    public boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            stack.addLast(s.charAt(i));
            if (stack.size() >= 3) {
                char c = stack.pollLast();
                char b = stack.pollLast();
                char a = stack.pollLast();
                if (!(a == 'a' && b == 'b' && c == 'c')) {
                    stack.addLast(a);
                    stack.addLast(b);
                    stack.addLast(c);
                }
            }
        }
        return stack.isEmpty();
    }
}

func isValid(s string) bool {
    stack := make([]byte, 0, len(s))
    for i := 0; i < len(s); i++ {
        stack = append(stack, s[i])
        if len(stack) >= 3 {
            n := len(stack)
            a, b, c := stack[n-3], stack[n-2], stack[n-1]
            if a == 'a' && b == 'b' && c == 'c' {
                stack = stack[:n-3]
            }
        }
    }
    return len(stack) == 0
}

相似题目

题目	难度	考察点
20. 有效的括号	简单	栈
71. 简化路径	中等	栈
1047. 删除字符串中的所有相邻重复项	简单	栈
1541. 平衡括号字符串的最少插入次数	中等	栈
946. 验证栈序列	中等	栈模拟

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/36698285