Check If Word Is Valid After Substitutions [leetcode easy]

Leetcode Question

Example 1,

Input: “aabcbc”
Output: true
Explanation: String ‘abc’ can be inserted in any order multiple time into a string; X and Y are both ‘abc’, Y is inserted into X resulting in the format ‘aYbc’.

Example 2,

Input: “abbcc”
Output: false

Solution 1: Replace ‘abc’ over and over again

time complexiity: O(n²)
space complexity: O(n)
runtime: 28 ms

1
2
3
4
5
6
7
def isValid(self, S: str) -> bool:
temp = ''
while S != temp:
temp = S
S = S.replace('abc', '')

return len(S) == 0

Solution 2: Use a stack to track the pattern ‘abc’

time complexiity: O(n)
space complexity: O(n)
runtime: 56 ms

1
2
3
4
5
6
7
8
9
10
11
12
13
def isValid(self, S: str) -> bool:
stack = []
for i in S:
if i == 'c':
if stack[-2:] != ['a','b']:
return False
else:
stack.pop()
stack.pop()
else:
stack.append(i)

return len(stack) == 0