we are going to make the logic for isbalanced function correct.This article is part of my efforts where i have made many mistakes while thinking about problem solution which iam just recording over here.Finally i will also have the correct anwser in the same language.As it is self explanatory no Explantion.
Test Case 1
Python
Failure
class Solution: def isequal(self,f,s): ok=[['(',')'], ['[',']'], ['{','}'], ] for i in ok: s=s.replace(i[1],i[0]) if f==s: return True else : return False def isBalanced(self, s): # code here s=s.strip() s.replace(" ","") n=len(s) #should be even if n%2!=0: return False m=n//2 f=s[:m] t=s[m:] t=t[::-1] return self.isequal(f,t)
My above program got failed at this test case "{[()()]}" in gfg.
Correct Approach
The algorithm uses a stack π to ensure that each opening bracket ((, {, [) has a corresponding and correctly ordered closing bracket (), }, ]). If all brackets are properly matched, the stack will be empty by the end of the string, indicating a valid sequence. ✅
πApproach
1️⃣ Iterate through the string:
Push each opening bracket ((, {, [) onto a stack. π₯
For each closing bracket (), }, ]):
Check if it matches the top of the stack (i.e., the most recent unmatched opening bracket). π
If the stack is empty or the bracket doesn’t match, the string is invalid, and we return false. ❌
2️⃣ Final check:
After iterating through the entire string, if the stack is empty, it means every opening bracket has a corresponding closing bracket, and the sequence is valid. π
c++ code
class Solution { public: bool ispar(string s) { if (s.length() <= 1) return false; stack<char> stack; for (int i = 0; i < s.length(); i++) { if (s[i] == '[' || s[i] == '{' || s[i] == '(') { stack.push(s[i]); } else if (stack.empty()) { return false; } else { if (s[i] == ')' && stack.top() != '(') return false; if (s[i] == '}' && stack.top() != '{') return false; if (s[i] == ']' && stack.top() != '[') return false; stack.pop(); } } return stack.empty(); } };
Python
Result successfull
this more clearly explain the logic of balancing stack
class Solution: def isBalanced(self, s): # code here stack=[] s=s.strip() s=s.replace(" ","") n=len(s) #should be even if n%2!=0: return False open="({[" # stack = deque() for i in s: if i in open: stack.append(i) else: if not stack: return False if i==']' and stack[-1]=='[': stack.pop() elif i==')' and stack[-1]=='(': stack.pop() elif i=='}' and stack[-1]=='{': stack.pop() else: return False return len(stack)==0
Another Short version
class Solution: def isBalanced(self, s): stack = [] s = s.strip().replace(" ", "") # Fix inplace mutation brackets = {'(': ')', '{': '}', '[': ']'} opening = brackets.keys() closing = brackets.values() for char in s: if char in opening: stack.append(char) elif char in closing: if not stack or brackets[stack[-1]] != char: return False stack.pop() return len(stack) == 0
Comments
Post a Comment