字符串—1003.检查替换后的词是否有效

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

题目

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

解题思路

本题和20题有效的括号相似，都可以用栈来解题。如：观察字符串“abcabcababcc”，‘c’就相当于20题的右括号，‘b’和‘a’就相当于左括号，则遍历字符串，遇到‘c’就依次弹出栈顶元素，依次判断是否为‘b’，‘a’，若不是或栈为空就直接返回False，否则遍历遇到‘a’或‘b’就存入栈。最后返回not stack，若最后栈为空，则有效。

代码

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        for ch in s:
        	if ch == 'c':
        		if not stack or stack.pop() != 'b':
        			return False
        		elif not stack or stack.pop() != 'a':
        			return False
        	else:
        		stack.append(ch)
        return not stack
        
           

至此，此题解答完毕