valid parenthesis string leetcode | valid parentheses string leetcode python | leetcode

Please like the video, this really motivates us to make more such videos and helps us to grow. thecodingworld is a community which is formed to help fellow student and professionals looking to crack the “coding interviews”.

We love solving and sharing problems which are frequently asked in technical interviews and voted by community at various websites.

✅ For more and upcoming updates join our community

#leetcode #python

[yitingyan]

Also can do this recursively:


def check_par (par_array, proc_stack):
right_ok = 0
for i in range(len(par_array)):
ch = par_array[i]
if ch == '(':
proc_stack.append(ch)
elif ch == ')':
if len(proc_stack) > 0:
proc_stack.pop()
else:
return -1
elif ch == '*':
# assume '*' is '('
proc_stack.append('(')
left_ok = check_par(par_array[i+1:], proc_stack)
if left_ok == 0:
proc_stack.pop()
else:
continue

# assume '*' is ' ':
if (i+1) < len(par_array):
empty_ok = check_par(par_array[i + 1], proc_stack)
else:
#This is the last element in the array:
empty_ok = 1
break
if empty_ok == 1:
continue
# assume '*' is ')':
if len(proc_stack) > 0:
proc_stack.pop()
right_ok = check_par(par_array[i+1:], proc_stack)
if right_ok == 0:
proc_stack.append('(')
else:
continue

if (left_ok == 0 and right_ok == 0 and empty_ok == 0):
return -1

if len(proc_stack) == 0:
return 1
else:
return 0

print(check_par(['(', ')', '*'], []))

print(check_par(['(', ')', '*', ')', '('], []))

[EdClarkHYCT]

Beautiful solution! I love it when a there’s a practical solution to a simple problem. Thanks for sharing! 👍👌

[smart-ml-coder]

two stack solution is great! works perfectly thanks brother!

[TheArbaaz-rntq]

Your videos are really helping me alot ! Thank you very much

[alinaalam]

I have a question regarding your first approach. Since, you're only checking if leftBalance = 0 or not and not checking whether the string starts with ")" or not, your solution will treat the string as a valid string. So, for example, if we have something like this: ")(", leftBalance would come out to be 0 and the function would return true. Maybe, I am missing something here. Can you please explain this?

[vishwanathkudtarkar]

Thanks, its good explanation but at line 52, seems you need to add further lines to give the correct reasult
if len(stack)>0:
return False
else:
return True

[RohitSingh-bhkb]

First solution is wrong bro, although your video still made it easier though

[rashibansal]

what about (*) ...you have considered * as ) one time one time as ( but I think there should be one more case where * will be considered as empty String.Correct me if I am wrong

[subhambanerjee]

your stack code is giving wrong answer the else will be life in the star_stack

[chaitu.petluri]

Does return false from the statements cover all the false solutions? Is there any proof, I am finding it hard to understand

[rashibansal]

no it isn't working for case like )(...here left will be 0 so code will return True

[lakshyajitlaxmikant]

Your first solution is wrong, gives output "false" for (*)

[nishanthsk]

Your approach will be wrong for ( ) ) * leftbalance=0 and will return true but it is false

[mayankrathi]

becoming a coder day by day bcoz of u..really thanks