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

【LetMeFly】1003.检查替换后的词是否有效

力扣题目链接：https://leetcode.cn/problems/check-if-word-is-valid-after-substitutions/

给你一个字符串 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" 。

 

提示：

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

方法一：栈

开辟一个字符栈，遍历字符串：

• 如果当前字符是a就入栈

• 如果当前字符是b就看栈顶是否是a，是a就将a换成b，不是a就返回false

• 如果当前字符是c就看栈顶是否是b，是b就让b出栈，不是b就返回false

• 时间复杂度$O(len(s))$

• 空间复杂度$O(len(s))$

AC代码

C++

class Solution {
public:
    bool isValid(string& s) {
        stack<char> st;
        for (char c : s) {
            if (c == 'a') {
                st.push('a');
            }
            else if (c == 'b') {
                if (st.empty() || st.top() != 'a') {
                    return false;
                }
                else {
                    st.pop();
                    st.push('b');
                }
            }
            else {
                if (st.empty() || st.top() != 'b') {
                    return false;
                }
                else {
                    st.pop();
                }
            }
        }
        return st.empty();
    }
};

Python

class Solution:
    def isValid(self, s: str) -> bool:
        st = []
        for c in s:
            if c == 'a':
                st.append('a')
            elif c == 'b':
                if not len(st) or st[-1] != 'a':
                    return False
                else:
                    st[-1] = 'b'
            else:
                if not len(st) or st[-1] != 'b':
                    return False
                else:
                    st.pop()
        return not len(st)

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/130470201