[leetcode] 1003. Check If Word Is Valid After Substitutions

[leetcode] 1003. Check If Word Is Valid After Substitutions

Description

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: trueExplanation:"" -> "abc" -> "aabcbc"Thus, "aabcbc" is valid.

Example 2:

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

Example 3:

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

Example 4:

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

Constraints:

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

分析

题目的意思是：字符串是由abc组成，现在判断这个字符串能够通过abc替换得到。我看了一下别人的思路，首先用栈把ab字符存储起来，然后遍历s，当遍历到c的时候看栈里面是否有ab，如果有则是valid，否则是不合法的。

代码

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

参考文献

​​[LeetCode] [Java/Python/C++] Stack Solution O(N)​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。