Algorithm
Problem Name: 1003. 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 int. More formally,tbecomestleft + "abc" + tright, wheret == tleft + tright. Note thattleftandtrightmay 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.
Constraints:
1 <= s.length <= 2 * 104sconsists of letters'a','b', and'c'
Code Examples
#1 Code Example with Python Programming
Code -
Python Programming
class Solution:
def isValid(self, S: str) -> bool:
stack = []
for i in S:
if i == 'c':
if stack[-2:] != ['a', 'b']:
return False
stack.pop()
stack.pop()
else:
stack.append(i)
return not stack
Input
s = "aabcbc"
Output
true