Valid Parenthesis String - Leetcode 678 - Python
Vložit
- čas přidán 24. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
💡 BINARY SEARCH PLAYLIST: • Binary Search
📚 STACK PLAYLIST: • Stack Problems
Python Code: github.com/neetcode-gh/leetco...
Problem Link: neetcode.io/problems/valid-pa...
0:00 - Read the problem
2:40 - Drawing Explanation
11:22 - Coding Explanation
leetcode 678
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#facebook #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
Python Code: github.com/neetcode-gh/leetcode/blob/main/678-Valid-Parenthesis-String.py
i almost committed a crime trying to solve this problem by myself thanks for helping me not become a felon
What the heck do you mean!
Thanks man, i watched your videos on the subway every day, and it helped me to spend that time studying. I appreciate it and I passed the tests for google, now in team matching!
So happy for you brother!
About that part where we reset leftMin to 0 if it's negative. Take for example a string that looks like this "(((***". After we have parsed this string our leftMax wil be 6 and our leftMin will be 0 which should return true because we can change every asterisk symbol for a right parenthesis symbol. But if we add another asterisk to that string "(((****" our leftMin will become -1. But in this case it doesn't make any sense for us to turn every asterisk into a right parenthesis because it will make the whole string invalid, that's why we treat one asterisk as an empty string and reset our leftMin to 0. And we don't afraid of a case like this "())" where we also should reset our leftMin because our leftMax will become less than 0 and it will return false.
Thanks for explaining, it is really a helpful comment
thanks!
great explanation!
"We are never going to recover from this" i spit out the cherry seeds from laughing hahahaha
Lol sometimes I get carried away
My two cents on the reset of negative leftMin, basically there're two sources we decrease the values of leftMin:
1. when we meet the ')'
2. encounter '*'.
If we have more than enough of ')' leftMax will become negative, and we will directly return false. However, if we don't return, and we get negative leftMin, which means we get more than enough '*' since we can transform the '*' to an empty string, this is how this -1 to 0 comes.
For eg,
(**
👍
Awesome. Thanks
This took a while to fully grasp. No chance I would ever come up with this myself under the pressure of a real interview. That being said tho, now that I do understand it I think this is one of the coolest solutions I’ve ever seen
An intuitive explanation: As we progress through the string, our minimum and maximum counts of unmatched left parentheses (`leftmin` and `leftmax`) dynamically change. If the `leftmin` becomes negative, it indicates that we've encountered more right parentheses than the total number of corresponding left parentheses and asterisks seen so far. In such cases, we can revise the previous characters to include an empty space, utilizing the wildcard '*' as an optional left parenthesis. This gives the string another chance to remain valid.
However, if the `leftmax` becomes negative, it signifies an irrecoverable situation. This occurs when, despite using all wildcards as left parentheses, the count of right parentheses exceeds the count of remaining unmatched left parentheses and asterisks. In essence, it means that the string cannot be balanced, rendering it invalid. This approach ensures that the string's validity is continuously monitored and maintained throughout the traversal.
For the first time, i didn't understand your explanation
Lol
First time I felt this way also
I know right. I feel so stuck.
same here
1. Why is the recursive + caching solution O(N^3) 5:20 ? Seems like it would be same as space complexity O(N^2).
2. The greedy approach is not well explained. Why will it return false iff the string is invalid?
leftMin and leftMax is our possibility range where leftMin is decrease choice, leftMax is increase choice. Since we only care if our leftMin can reach 0, if leftMin < 0, we reset it to 0 to eliminate other invalid possibilities.
A good explanation for the reason why we need a special resetting work for and only for leftmin can be:
A string can be invalid only if either it contains more left parentheses than right parentheses and vice versa or their positions violate the balance rule.
Leftmax can help us detect all possible violations but one: some left parentheses do not have matching right parentheses. We leave this mission to leftmin.
We traverse the string for the left to the right, and the leftmin is responsible for recording the most possible choices of the right parenthesis. However, a right parenthesis can never match a left one which is right to it.
So, whenever leftmin is less than zero, we will have no other choices apart from considering it(the character we are visiting) not existing and resetting it(leftmin) to zero. By doing that, we assure that we will never match a right parenthesis to a left one which is right to it.
Therefore, upon traversing the string, if leftmin is still larger than zero, we can be certain that there are unmatched left parentheses and return false. We can also be certain that every left parenthesis is matched otherwise, and since all possible 'right parenthesis' violations would have been detected by leftmax during the traversal, if we can finish the traversal, it is certain that every right parenthesis is matched, so it's safe to return true
Very helpful, thanks
I have this question today as my daily mission and I struggle a lot using stack with 2 times iterating the stack elements.
Thanks for your video and I have a better solution with straightforward checking the string valid
i love you daddy neetcode
I was really conflicted about why we reset leftMin whenever we fall below 0, but then convinced myself with this argument:
One way to think about this is we do -1 from leftMin only for ) and *
And while ) is definitive, * can have 3 possible states. We always assume ) and if we are wrong, then it could be either of the other 2
If c == ) and leftMin < 0, that would mean our assumption that previous * was ) is wrong and it could be "" or (
Eg: (*) or (*))
If c == * and leftMin < 0, that would mean our assumption that * was ) is wrong and it must be "" or )
Simple argument is, at any point of time we can have count(")")
if leftmin goes below negative we remove the possibility of that * being left parenthesis because that entire expression will be invalid
This might be one of the most intelligent solutions I've seen. Never in a million years would I have substituted a backtracking approach for a multi-variable tracker
This is the most brilliant solution, the mathematical correcteness of this solution is very clear.
"we will never recover from this" - yes we will never recover from the trauma this question causes
Just amazing !! Perfect explanation of the thought process involved !!
Hey man, thanks for all your effort and congrats on your recent job! I was wondering if you could make a video for Leetcode problem 2115. Find all Possible Recipes? I'm having a hard time trying to understand it. Thanks
Hi NeetCode, I noticed that this this problem is under "Stack" and the actual code in Java use Stack, but your video explanation is something else. What is preferred?
nice approach! thanks!
I'm thinking O(n). You can loop through the array and have a counter that you add 1to if the parenthesis is left and remove 1 if the parenthesis is right. And have a seperate counter for the *. In every interation you check if the parenthesis counter is negative. If it is you make sure that the wildcard counter is bigger than abs(parenthesis counter). And at the last iteration you check if wildcard counter is equal to or bigger than abs(paranthesis counter).
This is incorrect,
We could have ***(((, this would return True, since # wild == # left,
But the position in which we encounter wild cards matters.
I implemented that solution,it failed and then i searched this video LOL
To understand this question, first see question without wild card with stack and variable approach then with this use two stacks of asstrick and open bracket then you realise you dont need to remember everyone of index of open braces and asstrick just difference between two top values, and if difference is negative at certain point you never gonna make valid string.
Thank You So Much for this wonderful video.......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Great solution 👍👍
Couldn't find the link for the DP or memorization solution, can anyone please let me know where I can find it?
The editorial for this problem on leetcode has all the solutions
Thanks!
Try to understand the greedy idea for hours but it does not work for me intuitively. So I come back to the 2 stacks solution. Thanks for the explanation. I have been using your Neetcode 150 every day since a month ago. Thanks a lot!
Can you share the 2 stacks solution?
@@prasad9012 Hope this help
```
class Solution:
def checkValidString(self, s: str) -> bool:
return self.checkValidString_2stacks(s)
def checkValidString_2stacks(self, s: str) -> bool:
main, star = [], []
for i, c in enumerate(s):
if c == "(":
main.append(i)
continue
if c == "*":
star.append(i)
continue
# if we see a right ), try to cancel the left (
if main:
main.pop()
elif star and star[-1] < i:
star.pop()
else:
return False
# If main stack has left parenthesis, try to cancel it with *
while main and star and star[-1] > main[-1]:
star.pop()
main.pop()
# If we cannot cancel the left parenthesis
if main:
return False
# as along as the main stack is empty, we do not care the star anymore.
return True
```
@@nguyentp2133 I prefer this.. this is intuitive one
@@nguyentp2133 Thanks for this solution. It's much easier to grasp.
Can anybody explain why the dp solution for this takes o(n^3) ?
I think it is a mistake. I think time complexity is O(N^2) too.
The cache size, worst-case is O(N^2) because the worst-case combinations of 'i' and 'left', both bounded by N.
NeetCode says each cache entry requires x N, but I don't think this is right. Every invocation simply calls itself again, with no loops, etc.
In the dp with memo solution, I can't understand why we would revisit the same place. In each call, we always increment the i position, in "dps(i+1,...)", so wouldn't we always have different i in the next recursive call, so never will have it in the cache?
Only if we decrement i, "dps(i-1,....)" I would think then we might see it already in the cache.
What am I missing?
But you call dfs multiple times for i + 1, right?
Also, every one of these invocations will split into more if another * is found. The end result is many calls to the same position and even with the exact same arguments.
Great video
Think of it this way…
If you have oversupply of ‘(‘ then you cannot get 0 leftMin value even if you turn all ‘*’ into ‘)’, thats what we did by subtracting 1 from leftMin when we see a ‘*’
If we have oversupply of ‘)’ at any point i in the string then we can’t have a solution even if we turn all ‘*’ into ‘(‘ before point i… that’s where leftMax turns negative
If we don’t have oversupply of either ‘(‘ or ‘)’ then we can guarantee that we have a solution
if(leftMax < 0 ) return false;
// even we selected * as ( still right parenthesis are more then left parenthesis
f(leftMin
please make a video on Find the Closest Palindrome
dude how you got this code . that was beautiful . but how would a beginner would get these thoughts ?
really good explanation! thank you
this question should be hard, not medium
DFS is king. Crystal clear logic. Solved in 25ms.
watched a minute because i thought the question will be hell to solve and I didnt wanna keep duct-taping my solutions but I am glad I stopped and did it myself and it was easier than expected.
An easier solution would be to use two stacks.
True however u sacrifice space
isnt a single counter of type int be the even easier solution?
@@arjuntt2604 I think it's relative.
It's more intuitive. I think he's going for a low mem solution here
@@yashpathak9285 i didn't get you,
isn't the memoization (dp) solution supposed to be O(N^2) time comp?
since we are filling a 2d array of at most size n*n ?
this is my solution: (simplified the syntax for non c++ users)
bool checkValidString(string s) {
int n = s.size();
map dp;
// i for index, op means number of opened parenthesis (lrft)
bool dfs = (int i, int op){
if(dp.find({i, op})) return dp[{i, op}];
if(op < 0) return false;
if(i == n) return op == 0;
bool res = false;
if(s[i] == '(' ) res = dfs(i+1, op+1);
else if(s[i] == ')' ) res = dfs(i+1, op-1);
else res = dfs(i+1, op+1) || dfs(i+1, op) || dfs(i+1, op-1);
return dp[{i, op}] = res;
};
return dfs(0,0);
}
Also the editorial mention O(n^2) for the solution 2d dp with memoization
I tried solving this with DP, there's no way I'd come up with the greedy solution in an interview myself LOL
Jesus, this is a tough one.
Well looks like the greedy solution is not for me lol
Some questions are not meant to start your day with
You have already uploaded a video of this problem (same kind)
Let him upload two right
I will just go with 2 Stack solution :P
Just watching the first 2 min of your video, enabled me to solve the problem in a few minutes. I appreciate you setting up the problem coherently, instead of just immediately giving the answer.
there is even a simpler greedy approach using O(n) space for a Stack
'''
public class Solution {
// Time = Space = O(n) Soln
public bool CheckValidString(string s) {
Stack open = new Stack(), star = new Stack();
for(int i=0;i0)
open.Pop();
else if(star.Count>0)
star.Pop();
else
return false;
while(open.Count>0)
if(star.Count==0 || star.Pop() < open.Pop())
return false;
return true;
}
}
'''
lol, this greedy is tuff to come in interviews
class Solution:
def checkValidString(self, s: str) -> bool:
c = 0
q = 0
for i in range(len(s)):
if s[i] == '*':
q += 1
elif s[i] == '(':
c += 1
else:
if c > 0 :
c -= 1
elif q > 0:
q -= 1
else:
return False
c = 0
q = 0
for i in range(len(s)-1, -1, -1):
if s[i] == '*':
q += 1
elif s[i] == ')':
c += 1
else:
if c > 0:
c -= 1
elif q > 0:
q -= 1
else:
return False
return True
i fails to understand why one single counter is not enough for this problem,
traverse through the string,
increment counter for open parenthesis and decrement it for closed parenthesis,
if counter goes negative at any time, means invalid, and if counter didn't reach 0 at the end, invalid,
isn't this very simple logic enough for this problem?
someone please correct me.
That would be the case only if there were no '*' - wild card. The wild card changes the whole game
With your method, (*)) will give 'False' but it's actually True since * can be replaced with (
The reason we reset the leftMin to 0 when negative is that we can not cancel a future '('. Think about a simple invalid example "*(".
bool solve( int i , int cnt , string &s){
if( i == s.length() ){
return cnt == 0;
}
bool ans = false;
if( s[i] == '('){
ans = solve(i+1 , cnt+1 , s);
}
else if( s[i] == ')' && cnt-1 >= 0){
ans = solve( i+1 , cnt-1 , s);
}
else{
bool ans2 = false;
if( cnt-1 >= 0 ) {
ans2 = solve(i+1 , cnt-1 ,s);
}
ans = solve(i+1 , cnt+1 , s) || solve(i+1 , cnt , s ) || ans2;
}
return ans;
}
bool checkValidString(string s) {
return solve( 0 , 0 , s);
}
this recursive relation is not working i want to know why .........plzzz anybody can help me
Pls solve the 3rd problem from today's contest.
I came up with an easier solution O(n) space O(1)
It requires two passes
class Solution {
public boolean checkValidString(String s) {
int conflicts=0;
int resolvers=0;
for(int i=0;i0)resolvers--;
else return false;
}
else{
conflicts--;
}
}
else resolvers++;
}
conflicts=0;resolvers=0;
for(int i=s.length()-1;i>=0;i--){
if(s.charAt(i)==')'){
conflicts++;
}
else if(s.charAt(i)=='('){
if(conflicts==0){
if(resolvers>0)resolvers--;
else return false;
}
else{
conflicts--;
}
}
else resolvers++;
}
return true;
}
}
bro i too had the same intuition , but i lacked at extra opening parenthesis , thanks for the code , now i learnt my mistake
class Solution {
public boolean checkValidString(String s) {
int check = 0;
int boost = 0;
for(int i =0;i
@@LOKESHE-wi2yd ohh nice
@@LOKESHE-wi2yd my brain worked really good 5 months ago now I've got brainrott cannot understand my own code
first comment.
very helpful , very clear, to the point with out confusion explain thans 🫂