Leetcode 1003. Check If Word Is Valid After Substitutions
Problem Explanation
The problem entails determining if a given string, S, can be made solely by a series of steps that involve repeatedly inserting the string "abc" in any valid string V. To insert "abc", split V into two parts, X and Y (either could be empty), and form a new string by concatenating X, "abc", and Y.
The strategy to solve this problem is to use a stack to keep track of each character in the string. The stack will simulate the process of inserting "abc" into the string. By looking at the top of the stack, we can understand whether the current configuration of the string could have been achieved by inserting "abc".
Walkthrough
Let's take an example string 'abcabc'.
- Start by splitting
abcabc
intoabc
andabc
. - The first part matches the valid string, now we need to verify whether the second part 'abc' is valid.
This shows that 'abcabc' string is valid.
Now let's take another example string 'abcabcababcc'.
- Start by splitting subjects
abcabcababcc
intoabc
andabcababcc
. - The left part is valid. Let's split the remaining
abcababcc
intoabc
andababcc
. - For the remaining part
ababcc
, we can split this intoab
andabcc
. - Insert 'abc' between
ab
andabcc
will getabcabcababcc
. - All parts are valid so the string is valid too.
Solution
Python
1 2python 3class Solution: 4 def isValid(self, S: str) -> bool: 5 # Stack for storing and matching the characters 6 stack = [] 7 for c in S: 8 if c == 'c': 9 # Case where there aren't enough elements for matching "abc" 10 if len(stack) < 2: 11 return False 12 b, a = stack.pop(), stack.pop() 13 # The last two elements don't match "b" and "a", invalid 14 if a != 'a' or b != 'b': 15 return False 16 else: 17 # Push other characters into stack 18 stack.append(c) 19 20 # If there are unmatched characters left, the string is invalid 21 return len(stack) == 0
Java
1
2java
3class Solution {
4 public boolean isValid(String S) {
5 Stack<Character> stack = new Stack<>();
6 for (char c : S.toCharArray()) {
7 if (c == 'c') {
8 if (stack.isEmpty() || stack.pop() != 'b')
9 return false;
10 if (stack.isEmpty() || stack.pop() != 'a')
11 return false;
12 }
13 else {
14 stack.push(c);
15 }
16 }
17 return stack.isEmpty();
18 }
19}
JavaScript
1
2javascript
3var isValid = function(S) {
4 let stack = [];
5 for(let char of S){
6 if(char === 'c'){
7 if(stack.length < 2) return false;
8 if(stack.pop() !== 'b') return false;
9 if(stack.pop() !== 'a') return false;
10 }
11 else stack.push(char);
12 }
13 return stack.length === 0;
14};
C#
1
2csharp
3public class Solution {
4 public bool IsValid(string S) {
5 Stack<char> stack = new Stack<char>();
6 foreach(char c in S) {
7 if (c == 'c') {
8 if (stack.Count < 2 || stack.Pop() != 'b')
9 return false;
10 if (stack.Count < 1 || stack.Pop() != 'a')
11 return false;
12 }
13 else {
14 stack.Push(c);
15 }
16 }
17 return stack.Count == 0;
18 }
19}
C++
1
2cpp
3class Solution {
4public:
5 bool isValid(string s) {
6 stack<char> stack;
7 for (char c : s){
8 if(c == 'c'){
9 if(stack.size() < 2)
10 return false;
11 if(stack.top() != 'b')
12 return false;
13 stack.pop();
14 if(stack.top() != 'a')
15 return false;
16 stack.pop();
17 } else {
18 stack.push(c);
19 }
20 }
21 return stack.empty();
22 }
23};
In the solution, we maintain a stack that stores characters, simulating the process of inserting "abc". Whenever we encounter the character 'c', we check if there are at least two elements on the stack and if the last two characters were 'b' and 'a' in that order. If this is not the case, the string is invalid. Else, we pop the last two characters from the stack. For any non-'c' character, we push it onto the stack. If there are no unprocessed characters by the end of the string, the string is valid.# Complexity Analysis
The time complexity for this solution is O(n), where n is the length of the string. We iterate through the string only once, at each step performing a constant amount of work. In the worst case, we push and pop each character once, which are both O(1) operations.
The space complexity is also O(n), as in the worst case, we might end up storing all characters of the string in the stack before we start popping any of them.
In usage, this algorithm will be most efficient when dealing with strings of length in the thousands or tens of thousands. For particularly large strings, the space demands of the stack might become prohibitive.
Optimizations
The provided solution is already quite efficient, but there are a few possible optimizations:
-
Early Exit: If the length of the string isn't a multiple of 3, we can return false immediately as there's no way to form the string with "abc" sections.
-
Embed the Pattern Matching: Instead of stacking all characters and then verifying if they match the "b" and "a" pattern when a "c" appears, alternately we could directly check during the iteration if the current character and the two prior ones match the "abc" pattern.
These changes wouldn't alter the complexity of the solution but could provide some small speed improvements.
Conclusion
The problem of checking if a string is made by repeating "abc" can be effectively solved by using a stack to keep track of string characters and match them with "abc". This solution is both easy to implement and understand, and works efficiently for large strings. Considering the simplicity and effectiveness of this approach, it serves as an excellent demonstration of how stacks can effectively be used in string manipulation tasks.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.