Hello this is Derek!
This is another blog from the series called LeetCode in Swift, where I solve LeetCode challenges in Swift, as I am in the middle of job hunting process and I need to prepare for possible upcoming coding interview.
This is an easy difficulty problem in LeetCode, which involves the usage of Stack technique.
What is stack to begin with?
A stack is a Last-In-First-Out (LIFO) data structure. It is used to push things onto the stack, and pop them off in the reversed order it was pushed.
With this in mind, let’s get started with today’s LeetCode problem.
Today’s challenge: Valid Parentheses
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
- Every close bracket has a corresponding open bracket of the same type.
Example 1:
Input: s = "()"
Output: trueExample 2:
Input: s = "()[]{}"
Output: trueExample 3:
Input: s = "(]"
Output: falseConstraints:
1 <= s.length <= 104sconsists of parentheses only'()[]{}'.
Approach and Thought Process
While Swift doesn’t offer stack properties or data structures by default, this can easily be created by using an array to hold the characters to behave like stack.
Our goal is to find whether the given string of parentheses is valid or not. Not only we have to consider if the count of opening and closing parentheses match, we also need to consider the order they are placed in.
We will first check if the string count is even or not. If it’s not even, we don’t even have to continue with our code as it’s not considered a valid parentheses. (Valid parentheses will always be even, no matter what).
Then we can initialize an array named stack, and iterate through every string to store the opening parentheses (i.e. “(“, “{“, “[“), and pop last matching parentheses if closing parentheses (i.e. “)”, “}”, “]”) has been found.
Step 1. Edge Case Check
As mentioned earlier, we will first check for the string count to make sure that it’s even count.
if s.count % 2 != 0 {
return false
}Step 2. Initialize Stack Array
var stack = [Character]()Step 3. Iterate Through `s` String
We use for loops to iterate through every input string in s to perform our stack implementation. For every opening parentheses encountered, we will append it to our stack.
for char in s {
switch char {
case "(", "[", "{":
stack.append(char) // append opening parentheses to our stack
/*
Every time we encounter closing parentheses,
we will pop last if we have a matching parentheses
*/
case ")":
guard stack.popLast() == "(" else { return false }
case "]":
guard stack.popLast() == "[" else { return false }
case "}":
guard stack.popLast() == "{" else { return false }
default:
return false
}
}Step 4. Return If Stack is Empty or Not
return stack.isEmptyIf input array had valid parentheses, we would end up with an empty stack as we would have popped all the parentheses. Therefore, if stack is empty, this will return true, and if stack still has any of the parentheses opening, it would return false, but since we are already using guard statement for each case, we would never reach to this point if’s not a valid parentheses.
So our complete code implementation would look like this:
class Solution {
func isValid(_ s: String) -> Bool {
if s.count % 2 != 0 {
return false
}
var stack = [Character]()
for char in s {
switch char {
case "(", "[", "{":
stack.append(char)
case ")":
guard stack.popLast() == "(" else { return false }
case "]":
guard stack.popLast() == "[" else { return false }
case "}":
guard stack.popLast() == "{" else { return false }
default:
return false
}
}
return stack.isEmpty
}
}Walkthrough Example
Let’s use a random example, s = “(){[]}”, as our test case.
First, we know that s.count equals to 6, which is even, so we can continue with our code. We then initialize our stack that will hold character elements to begin our iteration.
Beginning with our first character, since it’s opening parentheses "(", we append to our stack. Stack is now:
stack = [“(“]
Then we encounter the closing parentheses ")”. We need to make sure whatever we are popping last is “(“. It is matching, so we can safely call popLast from the stack. Stack is now:
stack = []
We then encounter opening parentheses “{“ so we append to our stack. We then encounter another opening parentheses “[“ so we append this to our stack as well. Stack is now:
stack = [“{“, “[“]
Next we encounter the closing parentheses “]”. We need to make sure, again, that whatever character we are popping last is matching parentheses of “[“. Our stack’s last character is indeed “[“, so we can pop last character from our stack. Stack is now:
stack = [“{“]
Next we encounter the closing parentheses “}”. Again, we check if last character we are popping is a matching pair of “{“, which it is, so we can pop last. Stack is now:
stack = []
As we have completed our iteration, we will return stack.isEmpty to check if it’s empty. It is empty, therefore it will return true, which indicates that this is a valid parentheses.
And we have successfully solved another problem, with great efficiency!
Time and Space Complexity Analysis
The time complexity of our solution is O(n) as we are iterating through each character in the input string exactly once.
Space complexity is also O(n) as we are pushing all of the opening parentheses to our stack in worst case scenario.
I hope this explanation was helpful, as I personally had to go through some trial-and-error of trying to count individual parentheses and removing them from the array.
Feel free to comment on this approach, share your ideas or if you have alternative ways of solving this and consider following me for more blogs!
Stay tuned for more LeetCode solutions in Swift.
Until then, happy coding everyone! 🔥
