原文链接: https://leetcode-cn.com/problems/check-if-word-is-valid-after-substitutions

英文原文

Given a string s, determine if it is valid.

A string s is valid if, starting with an empty string t = "", you can transform t into s after performing the following operation any number of times:

• Insert string "abc" into any position in t. More formally, t becomes tleft + "abc" + tright, where t == tleft + tright. Note that tleft and tright may be empty.

Return true if s is a valid string, otherwise, return false.

 

Example 1:

Input: s = "aabcbc"
Output: true
Explanation:
"" -> "abc" -> "aabcbc"
Thus, "aabcbc" is valid.

Example 2:

Input: s = "abcabcababcc"
Output: true
Explanation:
"" -> "abc" -> "abcabc" -> "abcabcabc" -> "abcabcababcc"
Thus, "abcabcababcc" is valid.

Example 3:

Input: s = "abccba"
Output: false
Explanation: It is impossible to get "abccba" using the operation.

Example 4:

Input: s = "cababc"
Output: false
Explanation: It is impossible to get "cababc" using the operation.

 

Constraints:

• 1 <= s.length <= 2 * 104
• s consists of letters 'a', 'b', and 'c'

中文题目

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

字符串 s 有效 需要满足：假设开始有一个空字符串 t = "" ，你可以执行 任意次 下述操作将 t 转换为 s ：

• 将字符串 "abc" 插入到 t 中的任意位置。形式上，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" 。

示例 4：

输入：s = "cababc"
输出：false
解释：执行操作无法得到 "cababc" 。

 

提示：

• 1 <= s.length <= 2 * 104
• s 由字母 'a'、'b' 和 'c' 组成

通过代码

高赞题解

**1.考察栈,所以用栈来解此题;

2.针对字母c,当前字母为c时,就pop b and pop a,如果能正常执行,则无误,反之则有错;

3.最后判断栈是否为空即可;

4.完结。**

    public boolean isValid(String S) {

        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < S.length(); i++) {

            if (S.charAt(i) == 'c') {

                if (stack.empty() || stack.pop() != 'b')

                    return false;

                if (stack.empty() || stack.pop() != 'a')

                    return false;

            } else {

                stack.push(S.charAt(i));

            }

        }

        return stack.isEmpty();

    }

以下方法适合刚入门的小伙伴

    public boolean isValid(String S) {

        while (S.contains("abc"))

            S = S.replace("abc", "");

        return S.equals("");

    }

统计信息

通过次数	提交次数	AC比率
12580	21708	58.0%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
有效的括号	简单