1003. Check If Word Is Valid After Substitutions LeetCode Solution
In this guide, you will get 1003. Check If Word Is Valid After Substitutions LeetCode Solution with the best time and space complexity. The solution to Check If Word Is Valid After Substitutions problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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 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: 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 * 104
s consists of letters 'a', 'b', and 'c'
1003. Check If Word Is Valid After Substitutions LeetCode Solution in C++
class Solution {
public:
bool isValid(string s) {
stack<char> stack;
for (const char c : s)
if (c == 'c') {
if (stack.size() < 2)
return false;
if (stack.top() != 'b')
return false;
stack.pop();
if (stack.top() != 'a')
return false;
stack.pop();
} else {
stack.push(c);
}
return stack.empty();
}
}; /* code provided by PROGIEZ */
1003. Check If Word Is Valid After Substitutions LeetCode Solution in Java
class Solution {
public boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (final char c : s.toCharArray())
if (c == 'c') {
if (stack.size() < 2)
return false;
if (stack.peek() != 'b')
return false;
stack.pop();
if (stack.peek() != 'a')
return false;
stack.pop();
} else {
stack.push(c);
}
return stack.isEmpty();
}
} // code provided by PROGIEZ
1003. Check If Word Is Valid After Substitutions LeetCode Solution in Python
class Solution:
def isValid(self, s: str) -> bool:
stack = []
for c in s:
if c == 'c':
if len(stack) < 2 or stack[-2] != 'a' or stack[-1] != 'b':
return False
stack.pop()
stack.pop()
else:
stack.append(c)
return not stack # code by PROGIEZ
