Recursion 003
#recursion #datastructures #devstudy #balancedparenthesis #boolean
The Problem:
Write a method that accepts a string containing open or closed parenthesis and returns true if the string has a balanced set of parenthesis. Use recursion if possible.
Using the 10DIME approach to making sure I understand the problem:
Input: a string of parenthesis
Output: boolean. true if balanced, false if not balanced
Definitions:
– balanced means that the string has the same amount of left brackets as right brackets
– not balanced means that there is an uneven amount of brackets
Instructions:
- make string an array and remove the commas
Solving through iteration idea:
2. IF ODD: I want to split the string into characters, check if there is an odd total amount of chars, if so, return false
3. IF EVEN: I could:
– iterate through, collect all left brackets, save the count
– collect all right brackets, save the count
– if they are the same, return true
Solving through recursion idea:
What is my repeating function?
What is happening each time the recursion is called?
i
Methods: N/A
Edge Cases:
– if array is empty
– if array only contains one type of bracket
ITERATIVE IMPLEMENTATION:
def is_balanced?(string)
return false if string.empty?
arr = string.chars.delete_if { |s| s == "," }
if arr.count.odd?
false
else
left = []
arr.each do |bracket|
if bracket == "("
left << bracket
arr.delete(bracket)
end
end
left.count == arr.count ? true : false
end
end
p is_balanced?("") == false
p is_balanced?("(") == false
p is_balanced?("(,)") == true
p is_balanced?("(,(,(,),)") == false
p is_balanced?("(,(,(,(,(") == false
p is_balanced?("(,(,(,),),)") == true