The scenario is you are given a string of parentheses and are tasked to check if they are valid.
The description from codewars: “Write a function that takes a string of parentheses, and determines if the order of the parentheses is valid. The function should return true if the string is valid, and false if it’s invalid.”
So this is a fun little challenge and I’ll admit that I got this wrong the first time. My first approach, keeping with my motto of doing it logically first, involved using a stack to keep track of parentheses. so you loop over every character and if the stack is empty, you push the current value into the stack. If it’s not empty and the last value is different from the current value then you pop the last value.
At the end of the loop, you check the length of the stack. If the stack is empty then you return true, otherwise, return false.
Keen-eyed readers will already see the problem here. What if we have an input like
"())(()"? This will return true because the center parentheses are not the same but it’s not a valid case.
The solution to that was to make sure they match during the check. So I updated the code to be
This works and will pass all the tests.
What are we really trying to accomplish? We just want to know if all the parentheses match. After thinking about it for a few seconds it dawned on me that I didn’t need the stack, I didn’t need the
reduce function, I didn’t even need to loop through all the characters and I could accomplish the task in fewer lines of code. how?
By removing all matching pairs until I had none left. I used the replace function to replace all occurrences of
() with an empty string.
Sometimes you just have to take a step back and look at your problem again. It’s easy to get lost in the “brilliance” of your first approach that you overlook the simplest solution to the problem.
How would you solve this problem? Let me know on Twitter @phoexer and as always happy coding.
Today I am working on a summation problem made to look like building a tower out of cubic bricks. It’s fun to brute force sometimes.
Coming back to Rust code after a bit of a hiatus with a simple problem… The Two-sum problem. Finding numbers in an array. Yay, fun.
King Pinn: I Salute You. I’m driving halfway across the country and this song is on repeat. Rest in Peace Tonderai Makoni. You were awesome.
After a few weeks off I’m back to business. This is just an update post detailing plans for the rest of the year.
At last we finally have the great reveal, our mystery project was implementing RSA encryption in rust.