Link:- https://leetcode.com/problems/check-if-word-is-valid-after-substitutions/
Summary:
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.
For Example:
Input:
s = "aabcbc"
Output:
true
Logic:
This can be solved with the stack. Traverse string and if s[i]!= 'c' then insert into stack.
Else, check if stack element at the top and next to the top is 'b' and 'a' respectively or not.
if no: return false, else remove the top two elements of the stack.
Repeat the above steps.
At last, check if the stack is empty or not.
Time Complexity:
O(n)
To view my solution:
No comments:
Post a Comment