Medium

题目描述

给定一个字符串 s，判断它是否有效。

如果字符串 s 有效，那么从一个空字符串 t = "" 开始，可以通过执行以下操作任意次数将 t 转换为 s：

  • 在 t 的任意位置插入字符串 "abc"。更正式地说，t 变为 tleft + "abc" + tright，其中 t == tleft + tright。注意 tleft 和 tright 可能为空。

如果 s 是有效字符串，返回 true，否则返回 false。

示例 1：

输入：s = "aabcbc"
输出：true
解释：
"" -> "abc" -> "aabcbc"
因此，"aabcbc" 是有效的。

示例 2：

输入：s = "abcabcababcc"
输出：true
解释：
"" -> "abc" -> "abcabc" -> "abcabcabc" -> "abcabcababcc"
因此，"abcabcababcc" 是有效的。

示例 3：

输入：s = "abccba"
输出：false
解释：无法通过操作得到 "abccba"。

约束条件：

  • 1 <= s.length <= 2 * 10^4
  • s 由字母 ‘a’、‘b’ 和 ‘c’ 组成

解题思路

解题思路

这道题的核心是理解题意：我们只能通过不断插入 “abc” 来构造字符串，反过来思考就是不断移除 “abc” 子串。

方法一：栈模拟（推荐）

  • 遍历字符串，将字符逐个压入栈
  • 当栈顶连续三个字符恰好是 “abc” 时，将它们弹出
  • 最终如果栈为空，说明字符串有效

方法二：字符串替换

  • 重复查找并删除字符串中的 “abc” 子串
  • 直到无法找到 “abc” 或字符串为空
  • 如果最终字符串为空则有效

方法三：计数法

  • 遍历字符串，维护 ‘a’ 和 ‘b’ 的计数
  • 遇到 ‘a’ 时 a_count++
  • 遇到 ‘b’ 时，需要有足够的 ‘a’，然后 b_count++
  • 遇到 ‘c’ 时，需要有足够的 ‘b’，然后各计数减1

栈方法最直观易懂，时空复杂度都比较优秀，是推荐解法。

代码实现

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for (char c : s) {
            st.push(c);
            if (st.size() >= 3) {
                string temp = "";
                for (int i = 0; i < 3; i++) {
                    temp = st.top() + temp;
                    st.pop();
                }
                if (temp != "abc") {
                    for (char ch : temp) {
                        st.push(ch);
                    }
                }
            }
        }
        return st.empty();
    }
};

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for c in s:
            stack.append(c)
            if len(stack) >= 3 and stack[-3:] == ['a', 'b', 'c']:
                stack.pop()
                stack.pop()
                stack.pop()
        return len(stack) == 0

public class Solution {
    public bool IsValid(string s) {
        Stack<char> stack = new Stack<char>();
        foreach (char c in s) {
            stack.Push(c);
            if (stack.Count >= 3) {
                char[] temp = new char[3];
                for (int i = 2; i >= 0; i--) {
                    temp[i] = stack.Pop();
                }
                if (new string(temp) != "abc") {
                    foreach (char ch in temp) {
                        stack.Push(ch);
                    }
                }
            }
        }
        return stack.Count == 0;
    }
}

var isValid = function(s) {
    const stack = [];
    for (const c of s) {
        stack.push(c);
        if (stack.length >= 3 && 
            stack[stack.length - 3]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)遍历字符串一次，每个字符最多入栈出栈一次
空间复杂度O(n)栈的最大空间复杂度为字符串长度

相关题目