Valid Parenthesis String | 4 Detailed Approaches | Leetcode 678 | codestorywithMIK
376Whatsapp Community Link : https://www.whatsapp.com/channel/0029Va6kVSjICVfiVdsHgi1A
This is the 90thVideo of our Playlist "Dynamic Programming : Popular Interview Problems".
In this video we will try to solve a very good problem : Valid Parenthesis String | Leetcode 678
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Valid Parenthesis String | 4 Detailed Approaches | Leetcode 678 | codestorywithMIK
Company Tags : META
My solutions on Github(C++ & JAVA) : https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/DP/Valid%20Parenthesis%20String.cpp
Leetcode Link : https://leetcode.com/problems/valid-parenthesis-string/
My DP Concepts Playlist : https://youtu.be/7eLMOE1jnls
My Graph Concepts Playlist : https://youtu.be/5JGiZnr6B5w
My Recursion Concepts Playlist : https://www.youtube.com/watch?v=pfb1Zduesi8&list=PLpIkg8OmuX-IBcXsfITH5ql0Lqci1MYPM
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Interview_DS_Algo
Instagram : https://www.instagram.com/codestorywithmik/
Facebook : https://www.facebook.com/people/codestorywithmik/100090524295846/
Twitter : https://twitter.com/CSwithMIK
Subscribe to my channel : https://www.youtube.com/@codestorywithMIK
Approach Summary :
**Approach-1 (Using Recursion + Memoization):**
This approach utilizes recursion along with memoization to solve the problem. It defines a recursive function to check if the given string is valid or not, considering different possibilities of treating '*' as '(', ')', or empty. Memoization is used to store already computed states, which reduces redundant computation. This approach has a time complexity of O(n^2) and a space complexity of O(n^2).
**Approach-2 (Using Bottom-Up Dynamic Programming):**
Here, bottom-up dynamic programming is employed to solve the problem. It defines a 2D DP table where each state represents whether a substring from index i to n-1 is valid or not, considering the count of open brackets. The algorithm iterates through the string from right to left, updating the DP table based on the current character and the previously computed states. This approach has a time complexity of O(n^2) and a space complexity of O(n^2).
**Approach-3 (Using Two Stacks):**
This approach utilizes two stacks to keep track of open brackets and asterisks encountered in the string. It iterates through the string, pushing open brackets and asterisks onto their respective stacks and popping them when encountering a closing bracket. The algorithm also handles cases where there are excess open brackets or asterisks using post-processing. This approach has a time complexity of O(n) and a space complexity of O(n).
**Approach-4 (Constant Space):**
This approach aims to solve the problem using constant space. It iterates through the string twice, first from left to right to count open brackets and then from right to left to count closing brackets. At each step, it updates the counts based on the current character. If the count of open or close brackets becomes negative at any point, it indicates invalidity. This approach has a time complexity of O(n) and a space complexity of O(1).
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
✨ Timelines✨
00:00 - Introduction
4:16 - Approach-1
15:44 - Coding Approach-1
20:00 - Approach-2
36:32 - Coding Approach-2
45:52 - Approach-3
57:36 - Coding Approach-3
1:48:00 - Approach-4
1:11:12 - Coding Approach-4
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #newyear2024