40 Evaluate Expression To True Boolean Parenthesization Memoized
Вставка
- Опубліковано 30 вер 2024
- Evaluate Expression To True-Boolean Parenthesization Memoized
Given a boolean expression with following symbols.
Symbols
'T' --- true
'F' --- false
And following operators filled between symbols
Operators
& --- boolean AND
| --- boolean OR
^ --- boolean XOR
Count the number of ways we can parenthesize the expression so that the value of expression evaluates to true.
Example:
Input: symbol[] = {T, F, T}
operator[] = {^, &}
Output: 2
The given expression is "T ^ F & T", it evaluates true
in two ways "((T ^ F) & T)" and "(T ^ (F & T))"
PROBLEM STATEMENT LINK:www.geeksforge...
Playlist Link: • Dynamic Programming | ... .
------------------------------------------------------------------------------------------
Here are some of the gears that I use almost everyday:
🖊️ : My Pen (Used in videos too): amzn.to/38fKSM1
👨🏻💻 : My Apple Macbook pro: amzn.to/3w8iZh6
💻 : My gaming laptop: amzn.to/3yjcn23
📱 : My Ipad: amzn.to/39yEMGS
✏️ : My Apple Pencil: amzn.to/3kMnKYf
🎧 : My Headphones: amzn.to/3kMOzM7
💺 : My Chair: amzn.to/385weqR
🛋 : My Table: amzn.to/3kMohtd
⏰ : My Clock: amzn.to/3slFUV3
🙋🏻♀️ : My girlfriend: amzn.to/3M6zLDK ¯\_(ツ)_/¯
PS: While having good gears help you perform efficiently, don’t get under the impression that they will make you successful without any hard work.
![[UA] NAVI проти G2 Esports | Blast Premier Fall Final](http://i.ytimg.com/vi/QWlIm4FGESQ/mqdefault.jpg)
11:10 for those whom are watching in flow.
This should be a pinned comment for those watching in flow.
Thanks man for this
🙏
this helps
thanks bro
Ekk hi to dil hai kitni baar jeetoge ye line shayd bhai ke liye hi likhi gayi thi :-)
Thanks bhai ✌️❤️
@@TheAdityaVerma you are one of the best tutor for students who want to learn DSA
@@TheAdityaVerma Bhaiya... Actually I'm from ECE and literally 😑 I didn't like DSA Before... It seemed me a nightmare coz I'm not from CODING background tbh...
But But after Watching your all Playlists 😇 I don't know how but I'm actually fall in love with DSA :)
Now, it seems that DSA is the Most interesting thing :)
But do you know, bcs of whom I fall in love with DSA?????
Well.... Bcs of YOU BHAIYA ❤️🙌 and your teaching styles... :)
And thanks for Your playlist 😊😊😊 bhaiya... :)
Now, I'm like - "Aise teachers colleges me kyon nhi hote hai? yrr😕"
Thanks again to you 🥺 and your each and every playlists are just at the top notch... :)
Please complete the dp playlist topics like Kandane's algorithm, dp on grids,etc.
Yes,please much needed
Check this out :
ua-cam.com/play/PLauivoElc3ggagradg8MfOZreCMmXMmJ-.html
@@himanshugiri4214 oho
@@hokkisthaal5820 ye himanshu flirt kar rahe hi na bhenchod..
Exactly bro this playlist is incomplete with kadane and dp on grid. 😢
Great video Bhai.
Easier way to add to map
string temp=to_string(i)+" "+to_string(j)+" "+to_string(isTrue);
Unordered map, In case someone's wondering
Some OJs like Leetcode doesn't like unordered_map for time. Gets TLE. So 2 DP arrays might be the way to go.
on GFG when we return the answer it should be ans%1003 as it is written in the problem description.
Thanks bro I have been searching for this for 2 hrs
@@surajsuryawanshi7835 me too
@Aditya Verma thanks a lot bhai.. It's a hard level question in GFG and you made it look so easy. This is the best youtube channel for coding!! must say
Thanks, if you like it, do share the channel among your friends and college !!
@@TheAdityaVerma definitely... Anyway I would have surely left DP for my placements, if I hadn't discovered ur videos... Could you please upload a playlist on interview questions on hashing... ?
To all those jinka GFG pe TLE aa raha hai,
I was getting TLE i.e. 1.96 seconds ki limit cross hori thi. For DP table, i was using VECTOR. So i replaced vector by Array and Mera solution 0.41 seconds me submit ho gaya.
Hope it fixes yours too :)
Thank you so much
www.geeksforgeeks.org/boolean-parenthesization-problem-dp-37/ try this. The optimization is done in the previous problem, is not done in this problem. The optimization can be found in GFG,
Thanks bro it helped .
39 of 50 (78%) done! I prefer the 3D array.
same
I have been following the entire DP series and trust me it is the best playlist for dp in youtube.
This question is more complicated than previous questions, but just watch the main logic 2-3 times and you will definitely understand it. Once you understand it, try coding it on your own.
Fair warning: It's going to get more complicated.
For those who are looking for an optimised solution similar to the Palindrome Partitioning, here is the entire code:
#include
using namespace std;
int BP(string &s, int i, int j, bool b, vector &dp)
{
if (i > j)
return false;
if (i == j)
{
if (b)
return s[i] == 'T';
else
return s[i] == 'F';
}
if (dp[i][j][b] != -1)
return dp[i][j][b];
int ans = 0;
for (int k = i + 1; k > s;
bool b = true;
vector dp(s.size() + 1, vector(s.size() + 1, vector(2, -1)));
int cost = BP(s, 0, s.size() - 1, b, dp);
cout
Legendary explanation sir ! Not many people have guts to go this basic to explain the concepts of DP . Thanks a lot sir .
Thanks a lot
( instead of filling comment section with thanks, just increment the counter, lets keep the comment section for "suggestions / improvement / query " ).
Sir Please don't say Thanks at the end. It's our Responsibility to say Thanks to You for this awesome DP series. So Thanks a lot. ❤️
My learning always read the problem description completely even if you know the problem.
I was getting wrong answer at GFG because the answer has to modulo with 1003.
The C++ Solution for the problem is :-
unordered_map mp;
int noOfWays(string S,int i,int j , bool isTrue)
{
if(i>j)
return 0;
if(i==j)
{
if(isTrue)
return S[i]=='T'?1:0;
else return S[i]=='F'?1:0;
}
string temp=to_string(i)+' '+to_string(j)+' '+to_string(isTrue);
if(mp.find(temp)!=mp.end())
return mp[temp];
int ans=0;
for(int k=i+1;k
why did u do %1003 ?
@@lifeofchetas given in question
thankyou so much buddy for helping out
Improved Memoization by using map for the recursive calls inside the for-loop as well
class Solution{
public:
unordered_map mp;
int solve(string S,int i,int j, bool isTrue)
{
if(i > j) return 0;
if(i == j) {
if(isTrue) {
return S[i] == 'T' ? 1 : 0;
}
else {
return S[i] == 'F' ? 1 : 0;
}
}
string key = to_string(i);
key.push_back(' ');
key.append(to_string(j));
key.push_back(' ');
key.append(to_string(isTrue));
if(mp.find(key) != mp.end()) {
return mp[key];
}
int ans = 0;
for(int k = i+1; k
bro why are we doing ans%1003
@@kunalgoel9608 Bro Gfg practice problem statement says "Your task is to complete the function countWays() which takes N and S as input parameters and returns number of possible ways modulo 1003." that is why I did it
@@gourangpathak4443 thanks bro
@@gourangpathak4443 class Solution{
static int countWays(int N, String S){
// code here
return solve(S,0,N-1,true);
}
static Map numbers = new HashMap();
static int solve(String s,int i,int j,boolean isTrue){
//base Condition
if(i>j){
return 0;
}
if(i==j){
if(isTrue==true){
return s.charAt(i)=='T'?1:0;
}else{
return s.charAt(i)=='F'?1:0;
}
}
//chek in map for value
String key=i+" "+j+" "+isTrue;
if(numbers.containsKey(key)){
return numbers.get(key);
}
// variable to store ans
int ans=0;
//choice diagram code
for(int k=i+1;k
thanks man
@@gourangpathak4443
Yrr aap bawal ho apka explanation ka koi jawab ni h 💯💥💥💯❤❤❤
Btw bhaiya, aap dp on fibonacci, LIS, kadan's algorithm and dp on grid ka videos ni upload kroge kya ??
Complete JAVA SOLUTION FOR THIS PROBLEM -->
public class Solution {
int mod;
HashMap memo = new HashMap();
public int cnttrue(String expr) {
mod = 1003;
return numWaysForType(expr, 0, expr.length() - 1, 'T');
}
int numWaysForType(String expr,int i, int j, char value)
{
if(i > j)
return 0;
if( i == j)
return expr.charAt(i) == value ? 1 : 0;
String key = i + " " + j + " " + value;
// String key = String.valueOf(i) ;
// key= key.concat(" ") ;
// key = key.concat(String.valueOf(j)) ;
// key= key.concat(" ") ;
// key= key.concat(String.valueOf(value)) ;
if(memo.containsKey(key))
return memo.get(key);
long ans = 0;
for(int k = i + 1; k
If(Dp's God==Aditya verma)
{
return true;
}
Else
{
Return (Forget About Solving problem);
}
Working code:
public class Solution {
static Map memoization;
public int cnttrue(String str) {
memoization= new HashMap();
int count = countBoolean(str, 0, str.length() - 1, true);
return count;
}
static int countBoolean(String str, int i, int j, boolean isTrue) {
if (i > j)
return 0;
if (i == j) {
if (isTrue)
return str.charAt(i) == 'T' ? 1 : 0;
else
return str.charAt(i) == 'F' ? 1 : 0;
}
String key = ""+i+j+isTrue;
if(memoization.containsKey(key))
return memoization.get(key);
int ans = 0;
for (int k = i + 1; k < j; k += 2) {
int lt = countBoolean(str, i, k - 1, true);
int lf = countBoolean(str, i, k - 1, false);
int rt = countBoolean(str, k + 1, j, true);
int rf = countBoolean(str, k + 1, j, false);
if (str.charAt(k) == '&') {
if (isTrue)
ans += lt * rt;
else
ans += lt * rf + lf * rt + lf * rf;
} else if (str.charAt(k) == '|') {
if (isTrue)
ans += lt * rf + lf * rt + lt * rt;
else
ans += lf * rf;
} else if (str.charAt(k) == '^') {
if (isTrue)
ans += lt * rf + lf * rt;
else
ans += lf * rf + lt * rt;
}
}
ans = ans % 1003;
memoization.put(key, ans);
// dp[i][j][getNumfrombool(isTrue)] = ans;
return ans;
}
}
Question link - practice.geeksforgeeks.org/problems/boolean-parenthesization/0
Please help in finding the bug in my code.
URL -ide.geeksforgeeks.org/P2ldnthQUD
Those who are getting TLE on gfg or any other website please follow this:
1) use a 3D dp array instead of unordered_map as the complexity of unordered_map is still O(N) in worst case due to collisions in hashing.
2) memoize at every call in the k loop too like @Aditya Verma has shown in palindrome partitioning optimization video.
3) (For the worst of edge cases) In the base condition i==j , before returning store value 0/1 (T/F) depending on outcome in you dp array then return.
I have personally tried this and it works. Hope this helps!
Thanks, bro, I did all the 3 points u mentioned, and my code got succeeded in GFG... TYSM.
But Did you have any optimization algo. in using unordered_map and getting passed in GFG ???? (AFTER considering 2nd & 3rd concepts above, in my code)
If yes, please share :)
Bro please paste your code here
@@rishabsinha8749 sure bro..
#include
#include
using namespace std;
// Better use 3D Matrix cuz we don't have to iteratively search in the matrix as we are doing with Map.
int dp[1001][1001][2]; //for storing every sub-problems ans.(Memoization)
int TBP(string s, int i, int j, bool output) // here boolean output is the subproblem expression o/p
{
if(dp[i][j][output] != -1)
return dp[i][j][output];
if(i>j) //invalid i/p
return dp[i][j][output] = 0;
if(i==j) //smallest valid i/p
{
if(output == true)
{
if(s[i] == 'T') // i& j index pointer always lies either on T or F
return dp[i][j][output] = 1;
else
return dp[i][j][output] = 0;
}
else if(output == false)
{
if(s[i] == 'F')
return dp[i][j][output] = 1;
else
return dp[i][j][output] = 0;
}
} ////Base Condition
int ans = 0;
for(int k=i+1; k>t;
while(t--)
{
memset(dp, -1, sizeof(dp));
int n;
cin>>n; //str length
string str;
cin>>str;
int TrueNoOfWaysParenthesize = TBP(str, 0 ,n-1 , true); //final value of expression to be evaluated true.
cout
@@ashishmohapatra4654 bro in base condition when i==j cant we directly do this if(output == true)
return dp[i][j][output] = 1;
but not what you did
if(i==j) //smallest valid i/p
{
if(output == true)
{
if(s[i] == 'T') // i& j index pointer always lies either on T or F
return dp[i][j][output] = 1;
else
return dp[i][j][output] = 0;
}
else if(output == false)
{
if(s[i] == 'F')
return dp[i][j][output] = 1;
else
return dp[i][j][output] = 0;
}
} ////Base Condition
@@ashishmohapatra4654 Bro my only qus. for this solution is what would be the optimum size of the 3D Matrix. As len of string mentioned in the problem is 1
your explanation was great but the code is giving tle at gfg,i request you to please solve that question and put the solution in description
www.geeksforgeeks.org/boolean-parenthesization-problem-dp-37/ try this. The optimization is done in the previous problem, is not done in this problem. The optimization can be found in GFG,
There is a mistake in the code. In the base condition
if(i > j)
return false;
will come. Not
if(i > j)
return true;
But it does not matter as the code wont reach that base case as k is always between (i, j) (i and j not inclusive)
return type is int and returning true / false ?
@@shriharikulkarni3986 true for 1 and false for 0 in cpp
no he is right, it should be return false/0 only
Code as explained in the video. Passed all test cases on gfg
unordered_map m;
int solve(string s, int i, int j, bool isTrue){
if(i>j) return 0;
if(i==j){
if(isTrue==true){
return s[i]=='T';
}
else{
return s[i]=='F';
}
}
string temp=to_string(i); temp.push_back(' ');
temp.append(to_string(j)); temp.push_back(' ');
temp.append(to_string(isTrue));
if(m.find(temp)!=m.end()){
return m[temp];
}
int ans=0;
for(int k=i+1;k
1003 se mod kyu kiya
@@roshansinghenc7745 on gfg according to question the required answer should be less than 1003 that is why mod is done
Map se TLE aa raha tha
to matrix use karli
This code will give tle in gfg. So you need to do 2 changes in the code to run:
1. Use 3D array instead of map as even an unordered map takes logn time to find the key and when the key is string the the time complexity will be O(s.length()logn) so it'll give tle.
2. Take int t[205][205][2] instead of int t[101][101][2] as the constraint in the question is wrong.
##CODE##
## IT WILL IN 0.76 SEC ##
#include
#define mod 1003
using namespace std;
int dp[205][205][2];
int solve(string s, int i, int j, bool isTrue){
if(i>j) return 0;
if(dp[i][j][isTrue]!=-1) return dp[i][j][isTrue];
if(i==j){
if(isTrue)
return s[i]=='T';
else
return s[i]=='F';
}
int ans=0;
for(int k=i+1; k> t;
int n;
while(t-- && cin >> n){
memset(dp, -1, sizeof(dp));
string s;
cin >> s;
cout
@Vishwajeet can you please explain to me why you used mod? Is it because of some constraints?
Thank ypu buddy 🔥😍✅
@@chirag-sg4kd it was asked in question and also to avoid int overflow.
Read properties of modulo lke : ( a * b) % c = ( ( a % c ) * ( b % c ) ) % c
thanks bro...i was just worrying were i was wrong and you helped a lot
Internally unordered_map is implemented using Hash Table, the key provided to map are hashed into indices of a hash table that is why the performance of data structure depends on hash function a lot but on an average, the cost of search, insert and delete from the hash table is O(1).
memoized code ;)
#include
#include
using namespace std;
unordered_map mp;
int mcm(string str,int i,int j,bool istrue)
{
if(i>j)
return false;
if(i==j)
{
if(istrue==true)
return str[i]=='T';
else
return str[i]=='F';
}
string temp="";
temp.push_back(str[i]);
temp.push_back(str[j]);
if(istrue)
temp.push_back('1');
else
temp.push_back('0');
if(mp.find(temp)!=mp.end())
return mp[temp];
int ans=0;
for(int k=i+1;k>str;
mp.clear();
int indi=0;
int indj=str.length()-1;
bool istrue=true;
cout
If you are doing in Java at GFG then you need to use 3D array instead of Map. Otherwise you will become frustrated after writing a long code after watching (48+28) minutes video.
can u plse tell me whats wrong with my java code...im getting output as 0 always
import java.util.*;
class Main
{
static int[][][] t;
static int lf,lt,rf,rt;
static int ans=0;
static int solve(String s,int i,int j,int o)
{
if(i>j){return t[i][j][o]=0;}
if(t[i][j][o]!=-1) return t[i][j][o];
if(i==j)
{
if(o==1)
{
if(s.charAt(i)=='T'){return t[i][j][o]=1;}
else {return t[i][j][o]=0;}
}
if(o==0)
{
if(s.charAt(i)=='T'){return t[i][j][o]=0;}
else {return t[i][j][o]=1;}
}
}
for(int k=i+1;k
for those who are getting time limit on gfg on this code, you also have to store the ans of subproblems lt, rt, lf,rf in 3d matrix
I think if I>j is should be return false
EARLIER I WAS USING THE MAP AS A MEMOIZATION METHOD BUT IT WAS GIVING TLE THEN I MOVED TO 3D MATRIX MEMOIZATION METHOD STILL IT WAS GIVING TLE ,,THEN I JUST APPLIED TWO LINES OF FAST AND MY CODE GOT ACCEPTED..THANKU
#include
using namespace std;
#define ll long long
#define fast ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL)
//unordered_mapmp;
long long int dp[501][501][3];
#define mod 1003
ll solve(string str,ll i,ll j,bool istrue){
if(i>j)return false;
if(i==j){
if(istrue==true){
return str[i]=='T';
}
else return str[i]=='F';
}
if(dp[i][j][istrue]!=-1){
return dp[i][j][istrue];
}
ll ans=0;
for(ll k=i+1;k>n;
string str;
cin>>str;
// mp.clear();
memset(dp,-1,sizeof(dp));
cout
This is the memoization solution , totally fine ,and all are same only one thing , you just need to use ans % 1003 , ( for avoiding the overflow)
int t[201][201][2];
int solve(string &s , int i , int j , bool isTrue){
//Base Case
if(i > j ) return 0;
//memoization check
if(t[i][j][isTrue] != -1){
return t[i][j][isTrue];
}
//Base case, if there is only one element
if( i == j){
if(isTrue == true) return s[i] == 'T';
else return s[i]== 'F';
}
//K loop
int ans = 0; // temp ans
// All possibilities for getting true and false as well
for(int k = i+1 ; k
use only if you facing diffcultly while using map solution
if the return type of the solve function is int then why (i>j)is returning true??
Just use 1 and 0 instead of True and False respectively
true represents 1 and false represent 0
If we store LT, LF, RT, RF too in the map , it will provide better optimization .
Eventually, recursion will save these i.e. LT, LF, RT, RF. when we will not have them in map and when we will ask recusrion to solve them then last line of the code will be executed for each of them, which is saving calls.
They will automatically get stored on their first function call
bro please start recursion and backtracking series ...I am waiting for it...😁😁
We all are waiting ! Plz 🙏🙏🏿🙏🏿🙏🙏🏿🙏🏿
aur bhai kya hal
Great Explanation. I also came up with a similar approach but the way of implementation and thought process is different.
Lets say we have input = {T^T^F*T&F...........T}
create a parent function which just counts the ways by splitting at different operands index.
e.g. for k = 1, check if (left part ^ right part == True) ->> increase count
for k = 3, check if (left part ^ right part == True) ->> increase count
for k = 5, check if (left part * right part == True) ->> increase count
at the end return count;
Now for evaluating left and right part separately, write a different evaluate function whose purpose is just to evaluate and return true or false. Of course evaluate function will also break the input expression at different operands. Code below :-
public class EvaluateExpressionToTrue {
static int count = 0;
static Map map = new HashMap();
public static void main(String[] args) {
String x = "T^T^F";
countWays(x.toCharArray(), 0, x.length() - 1);
System.out.println(count);
}
private static int countWays(char[] x, int i, int j) {
for (int k = i + 1; k < j; k = k + 2) {
System.out.println("evaluating in parent - " + i + "::" + k + "::" + j);
int lRes = evaluate(x, i, k - 1);
int rRes = evaluate(x, k + 1, j);
int res = getResult(lRes, rRes, x[k]);
if (res == 1)
count++;
}
return count;
}
private static int evaluate(char[] x, int i, int j) {
if (i == j) return 1;
for (int k = i + 1; k < j; k = k + 2) {
System.out.println("evaluating - " + i + "::" + k + "::" + j);
String key = i + ":" + k + ":" + j;
if (!map.containsKey(key)) {
int lRes = evaluate(x, i, k - 1);
int rRes = evaluate(x, k + 1, j);
int res = getResult(lRes, rRes, x[k]);
if (res == 1) {
map.put(key, 1);
return 1;
}
}
map.put(key, 0);
}
return 0;
}
private static int getResult(int lRes, int rRes, char operand) {
int res;
switch (operand) {
case '|':
res = lRes | rRes;
break;
case '&':
res = lRes & rRes;
break;
case '^':
res = lRes ^ rRes;
break;
default:
throw new IllegalStateException("Unexpected value: " + operand);
}
return res;
}
}
how can we return boolean in base condition in a func returning integer
Can't we use two 2D matrix one for true and one for false??
The memoized code done using MAP os giving TLE in gfg. If anyone has done it...Kindly send the code.... "Memoized code done by Mapping"
Map is giving TLE on gfg, better use 3D Matrix cuz we don't have to iteratively search in matrix as we are doing with Map.
But if you get the optimized code, help me out too!
It will also work with map and not give TLE just use mapname.count(key) (will take O(1) time) instead of mapname.find. :) Happy learning!!
wrong it takes logarithmic in size, same as find
@@jeetgupta1107 logarithmic time i.e log(n) only in case of map i.e ordered_map not in case of unordered map.
@rahulrajsjs22 then in case of unordered_map it will take linear size
if we take a 3d table as t[2][1001][1001] its easier to imagine. because now there are 2 layers of nxn stacked on top of each other. 1 layer depicts when isture is true and the other depicts when istrue is false.
if we take t[1001][1001][2] then its the same thing except sideways. 1001 layers of 1001x2 tall strips which is same as 2 1001x1001 matrices side by side
Jump to 10:00 if you know why we need memoization.
whenever u say in last .. "I hope samajh aa gaya hoga" .. dude seriously no need of saying that.
unordered map me find function ki complexity O(N) hoti hai , shouldnt it be replace by ordred map ?
not getting all testcases passed in IB
Just to ask isn't it good idea to also store values of LT, LF, RT, RF values for further optimization ??
By mistake, you have written the base condition i>j : True
Hint for javascript coders using a map will timeout on gfg use 3d array
Python code:
class Solution:
def countWays(self, N, S):
# code here
sDict={}
def solve(i, j, isTrue):
key = str(i)+'_'+str(j)+'_'+str(isTrue)
if i>j:
sDict[key] = 0
return 0
elif i==j:
if isTrue and S[i]=='T':
sDict[key] = sDict.get(key, 0)+1
return 1
elif not isTrue and S[i]=='F':
sDict[key] = sDict.get(key, 0)+1
return 1
else:
sDict[key]=0
return 0
if key in sDict:
return sDict[key]
temp=0
for k in range(i+1, j, 2):
key1 = str(i)+'_'+str(k-1)+'_'+str(1)
key2 = str(i)+'_'+str(k-1)+'_'+str(0)
key3 = str(k+1)+'_'+str(j)+'_'+str(1)
key4 = str(k+1)+'_'+str(j)+'_'+str(0)
if key1 in sDict:
lt = sDict[key1]
else:
lt = solve(i, k-1, 1)
sDict[key1] = lt
if key2 in sDict:
lf = sDict[key2]
else:
lf = solve(i, k-1, 0)
sDict[key2]=lf
if key3 in sDict:
rt = sDict[key3]
else:
rt = solve(k+1, j, 1)
sDict[key3]=rt
if key4 in sDict:
rf = sDict[key4]
else:
rf = solve(k+1, j, 0)
sDict[key4]=rf
if S[k]=='&':
if isTrue:
temp = temp+(lt*rt)
else:
temp = temp+(lt*rf)+(lf*rf)+(lf*rt)
elif S[k]=='|':
if isTrue:
temp = temp+(lt*rf)+(lt*rt)+(lf*rt)
else:
temp = temp+(lf*rf)
elif S[k]=='^':
if isTrue:
temp = temp + (lt*rf)+(lf*rt)
else:
temp = temp + (lt*rt)+(lf*rf)
sDict[key]=temp
return sDict[key]%1003
return solve(0, N-1, 1)
15:52
Aditya Verma - Humna 1001 pe 1 extra laga dia, kyo?
Me - Shagun ka lia?
was anyone able to solve this question from scratch without any help?
How are you returning true and false in base condition of the function is int type
it returns 0 or 1
gfg mein bina bottom up test pass nhi ho rhe....
Python Memoized using 3D Table:
S = ['T', '|', 'F', '&', 'T', '^', 'T']
n = len(S)
# T size: 2 x n x n
T = [[[-1 for _ in range(n)] for _ in range(n)] for _ in range(2)]
def Solve(S, i, j, isTrue):
if i > j:
return False
if i == j:
if isTrue:
return S[i] == 'T'
else:
return S[i] == 'F'
if T[isTrue][i][j] != -1:
return T[isTrue][i][j]
count = 0
for k in range(i+1, j, 2):
LT = Solve(S, i, k-1, True)
LF = Solve(S, i, k-1, False)
RT = Solve(S, k+1, j, True)
RF = Solve(S, k+1, j, False)
if S[k] == '&':
if isTrue:
count = count + LT * RT
else:
count = count + LT * RF + LF * RT + LF * RF
elif S[k] == '|':
if isTrue:
count = count + LT * RF + LF * RT + LT * RT
else:
count = count + LF * RF
elif S[k] == '^':
if isTrue:
count = count + LT * RF + LF * RT
else:
count = count + LT * RT + LF * RF
T[isTrue][i][j] = count
return count
count = Solve(S, 0, len(S) - 1, True)
print(count)
Hey, I wrote almost the same code; however, for one of the test cases, the output I am getting is very large. Have you faced this ?
function int k hai to return true or false kyu krrhe
I am not able to pass all the test cases at interviewbit using the below code.
can anyone fix it....
unordered_map mp;
int solve(string s, int i, int j,bool istrue)
{
// if(i>j)
// return true;
if(i==j)
{
if(istrue==true)
return s[j]=='T';
else
return s[j]=='F';
}
string temp = to_string(i);
temp.push_back(' ');
temp.append(to_string(j));
temp.push_back(' ');
temp.append(to_string(istrue));
if(mp.find(temp)!=mp.end())
return mp[temp];
int ans=0;
for(int k=i+1; k
I guess the TC for the GFG problem is updated, i was getting TLE but passed all test cases after optimization explained in earlier videos
Thankyou @Aditya Verma sir
how did you know you passed all test cases
@@vasudevparmar9876 It was accepted at GFG & had tested some manually.
His understanding of DP is so good.
In case your code is not getting accepted with Map, you can do it with 3D dp:
static final int MOD = 1003;
static int[][][] dp;
public static int countWays(int n, String s) {
dp = new int[n][n][2];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dp[i][j][0] = -1;
dp[i][j][1] = -1;
}
}
return solve(s, 0, n - 1, true);
}
static int solve(String s, int i, int j, boolean isTrue) {
// Base case
if (i > j) return 0;
// if only one character is there
if (i == j) {
if (isTrue) return s.charAt(i) == 'T' ? 1 : 0;
else return s.charAt(i) == 'F' ? 1 : 0;
}
int isTrueInt = isTrue ? 1 : 0;
if (dp[i][j][isTrueInt] != -1) {
return dp[i][j][isTrueInt];
}
int ans = 0;
for (int k = i + 1; k < j; k += 2) {
int lt, lf, rt, rf;
// Check memo array before calling solve for left and right subproblems
if (dp[i][k - 1][1] != -1) {
lt = dp[i][k - 1][1];
} else {
lt = solve(s, i, k - 1, true);
}
if (dp[i][k - 1][0] != -1) {
lf = dp[i][k - 1][0];
} else {
lf = solve(s, i, k - 1, false);
}
if (dp[k + 1][j][1] != -1) {
rt = dp[k + 1][j][1];
} else {
rt = solve(s, k + 1, j, true);
}
if (dp[k + 1][j][0] != -1) {
rf = dp[k + 1][j][0];
} else {
rf = solve(s, k + 1, j, false);
}
if (s.charAt(k) == '&') {
if (isTrue) ans = (ans + lt * rt) % MOD;
else ans = (ans + lf * rf + lf * rt + lt * rf) % MOD;
} else if (s.charAt(k) == '|') {
if (isTrue) ans = (ans + lt * rt + lt * rf + lf * rt) % MOD;
else ans = (ans + lf * rf) % MOD;
} else if (s.charAt(k) == '^') {
if (isTrue) ans = (ans + lt * rf + lf * rt) % MOD;
else ans = (ans + lt * rt + lf * rf) % MOD;
}
}
dp[i][j][isTrueInt] = ans;
return ans;
}
Java HashMap Memoization Solution (Bottom up) || Aditya Verma Approach
class Solution {
static int countWays(int n, String s) {
return solve(s.toCharArray(), 0, n - 1, 1, new HashMap());
}
private static int solve(char[] s, int i, int j, int isTrue, Map map) {
// Base Condition
if (i > j) return 0;
if (i == j) {
if (isTrue == 1) return s[i] == 'T' ? 1 : 0;
else return s[i] == 'F' ? 1 : 0;
}
String key = i + "-" + j + "-" + isTrue;
int res = map.getOrDefault(key, -1);
if (res != -1) return res;
long ways = 0;
for (int k = i + 1; k
Using matrix is easier as compared to map bcz we don't need to visualise the matrix
the base case is different from what u explain in the previous video plz edit it here u return true where the previous u return false
recursion ki time complexity kya hai? before optimization
Constraints are given wrong in GFG.. If someone is facing tle or sigsegv error, then initialise your dp[205][205][2] like this.. 105 is out of bound
Could you run the program??
@@priyanshu.tiwari Yes
@@prabhanshuchauhan4150 i tried, it still didn't work, can u share your code once?
@@priyanshu.tiwari you can ignore solve2 function. That is for bottom-up dp.
@@prabhanshuchauhan4150 hey, thanks, it worked :), I wrote a similar code but it was giving TLE, ide.geeksforgeeks.org/x0vJ1Ba2Tu
class Solution {
public:
int mod = 1003;
int solve(int i, int j, string s, vector& dp, bool istrue) {
if (i > j) {
return 0;
}
if (i == j) {
if (istrue == true) {
return s[i] == 'T';
} else {
return s[i] == 'F';
}
}
if (dp[i][j][istrue] != -1) {
return dp[i][j][istrue];
}
int ans = 0;
for (int k = i + 1; k < j; k = k + 2) {
int lt = solve(i, k - 1, s, dp, true);
int lf = solve(i, k - 1, s, dp, false);
int rt = solve(k + 1, j, s, dp, true);
int rf = solve(k + 1, j, s, dp, false);
if (s[k] == '&') {
if (istrue == true) {
ans = (ans + lt * rt) % mod;
} else {
ans = (ans + (lf * rf) + (lt * rf) + (rt * lf)) % mod;
}
} else if (s[k] == '|') {
if (istrue == true) {
ans = (ans + (lt * rt) + (lt * rf) + (rt * lf)) % mod;
} else {
ans = (ans + lf * rf) % mod;
}
} else if (s[k] == '^') {
if (istrue == true) {
ans = (ans + (lt * rf) + (rt * lf)) % mod;
} else {
ans = (ans + (lt * rt) + (lf * rf)) % mod;
}
}
}
return dp[i][j][istrue] = ans;
}
int countWays(int n, string s) {
bool istrue = true;
vector dp(n, vector(n, vector(2, -1)));
return solve(0, n - 1, s, dp, istrue);
}
};
Still getting WRONG ANSWER!! Just dont know what's wrong,my code or the java compiler!!
public static int EvaluateExpressionToTrueDP(String s, int i, int j, int isTrue) {
if (i > j) return 0;
if (i == j) {
if (isTrue == 1) {
return (s.charAt(i) == 'T') ? 1 : 0;
} else {
return (s.charAt(i) == 'F') ? 1 : 0;
}
}
if (DP[i][j][isTrue] != -1)
return DP[i][j][isTrue];
int answer = 0, leftTrue, rightTrue, leftFalse, rightFalse;
for (int k = i + 1; k < j; k += 2) {
if (DP[i][k - 1][1] != -1) {
leftTrue = DP[i][k - 1][1];
} else
leftTrue = EvaluateExpressionToTrueDP(s, i, k - 1, 1);
if (DP[i][k - 1][0] != -1) {
leftFalse = DP[i][k - 1][0];
} else
leftFalse = EvaluateExpressionToTrueDP(s, i, k - 1, 0);
if (DP[k + 1][j][1] != -1) {
rightTrue = DP[k + 1][j][1];
} else rightTrue = EvaluateExpressionToTrueDP(s, k + 1, j, 1);
if (DP[k + 1][j][0] != -1) {
rightFalse = DP[k + 1][j][0];
} else
rightFalse = EvaluateExpressionToTrueDP(s, k + 1, j, 0);
if (s.charAt(k) == '&') {
if (isTrue == 1) {
answer += leftTrue * rightTrue;
} else {
answer += leftFalse * rightFalse + leftTrue * rightFalse + leftFalse * rightTrue;
}
} else if (s.charAt(k) == '|') {
if (isTrue == 1) {
answer += leftTrue * rightTrue + leftFalse * rightTrue + leftTrue * rightFalse;
} else {
answer += leftFalse * rightFalse;
}
} else if (s.charAt(k) == '^') {
if (isTrue == 1)
answer += leftFalse * rightTrue + leftTrue * rightFalse;
else
answer += leftFalse * rightFalse + leftTrue * rightTrue;
}
DP[i][j][isTrue] = answer;
}
return answer;
}
iska code khi bhi nhi hai using hashmap in java ,I have tried but all test cases aren't passing
if you are getting TLE error in gfg...we have to take at last (ans%1003)...it is given in qn too, I forgot to read the qn properly and was wasting my time for half an hour....hope this helps !
my code is still showing TLE
unordered_map mp;
int solve(string s, int i, int j, bool isTrue) {
if (i > j)
return 0;
if (i == j) {
if (isTrue)
return s[i] == 'T';
else
return s[i] == 'F';
}
string temp = to_string(i) + " " + to_string(j) + " " + to_string(isTrue);
if (mp.find(temp) != mp.end())
return mp[temp];
int ans = 0;
for (int k = i + 1; k
public static int solve(String s, int i, int j, boolean isTrue) {
if (i > j) return 0;
if (i == j) {
if (isTrue) {
return s.charAt(i) == 'T' ? 1 : 0;
} else {
return s.charAt(i) == 'F' ? 1 : 0;
}
}
if (map.containsKey(i + ":" + j + isTrue)) {
return map.get(i + ":" + j + isTrue);
}
int ans = 0;
for (int k = i + 1; k < j; k += 2) {
int lt = solve(s, i, k - 1, true);
int rt = solve(s, k + 1, j, true);
int lf = solve(s, i, k - 1, false);
int rf = solve(s, k + 1, j, false);
if (s.charAt(k) == '&') {
if (isTrue) {
ans = ans + (lt * rt);
} else {
ans = ans + (lt * rf) + (rt * lf) + (rf * lf);
}
}
else if (s.charAt(k) == '|') {
if (isTrue) {
ans = ans + (lt * rf) + (rt * lf) + (rt * lt);
} else {
ans = ans + (lf * rf);
}
}
else {
if (isTrue) {
ans = ans + (lt * rf) + (rt * lf);
} else {
ans = ans + (lt * rt) + (rf * lf);
}
}
}
map.put(i + ":" + j + isTrue, ans);
return map.get(i + ":" + j + isTrue);
}
Do not use 3D vectors in GFG use 3D array or you will get TLE as vectors have huge overhead.
brother your comment saved me ,I began doubt my approach can you explain why this is causing problem
I actually don't know why vectors are slow but i faced similar issues in LeetCode also where changing the vector to Array reduces the running time by half.
What is the time complexity of this solution? Please help in finding out the complexity.
it think O(n^3)
@@voldemort576 How ? please explain
@@yadneshkhode3091 at worst we will need to calculate every single cube of matrix. so the time complexity would be. O(N*N*2).
N is length of the string.
Your videos really helped me grasp dp. Keep up the good work! And please make a graph playlist!
to.string ko python m kaise krna h anyone help!!!!!!
FULL GFG SUBMITTED CODE:
class Solution{
public:
unordered_map m;
int solve(string &s, int i, int j, bool isTrue)
{
if(i>j) return 0;
if(i==j)
{
if(isTrue)
{
return s[i]=='T';
}
else
{
return s[i]=='F';
}
}
string temp= to_string(i) + " " + to_string(j) + " " + to_string(isTrue);
if(m.find(temp)!=m.end())
{
return m[temp];
}
int ans=0;
for(int k=i+1; k
I am getting wrong answers for some cases on gfg please help me
Can someone help me? Is code me TLE aa rha mera.
@Aditya Verma your code is not working on gfg plzz check
yep ! i even tried to optimize the code by the technique taught in the palindromic partitioning but its still giving TLE on gfg ...@Aditya Verma bro can you suggest some other optimization technique ?
Yup bro,it is giving tle in gfg,even if i optimised lt,rt,lf,rf using memoization
i space j space kyu likh rhe??
Anyone...
bhyi code bhi daaldiya kro yrr ,bilkul bhi nhi chl rha ,kya glti hain no idea its request
What is time complexity for this code ??
n^2 with matrix
with map it'll be slightly more
unordered_mapmp;
class Solution{
public:
int solve(string s,int i,int j,bool isTrue)
{
//base condition
if(i>j)
return false;
if(i==j)
{
if(isTrue==true)
return s[i] == 'T';
else
return s[i] == 'F';
}
string temp = to_string(i) + ' ';
temp += to_string(j) + ' ';
temp += to_string(isTrue);
if(mp.find(temp) != mp.end())
return mp[temp];
else
{
int ans = 0;
for(int k=i+1;k
Ye Wa kyu de rha he ? what's wrong in my code
class Solution{
unordered_mapmp;
int solve(int i,int j,string s,bool istrue){
if(i>j)return 0;
if(i == j){
if(istrue == true){
return s[i]=='T';
}
else{
return s[j]=='F';
}
}
string temp=to_string(i)+" "+to_string(j)+" "+to_string(istrue);
if(mp.find(temp) != mp.end()){
return mp[temp];
}
int ans = 0;
for(int k = i+1 ; k
Bhaiya digit dp ka bhi kuch padha do
Sir code me count increase Kaha par hora sir
can we use hashmap??? that would have been faster in terms of search time so...
Hashmap isn't faster than array, array are index based data structure which have worst case O(1) time access to an element, Hashmap we do say it O(1) asymptotically through amortized analysis but it will definately take more running time than an arrays or a matrix.
why global variable doesn't work on interviewbit?
it always give wrong ans.
GFG Updated it's constraint and looking for an iterative approach / complete matrix approach, so any plan of that video in the list?
following
Nope Memoization is working . I Successfully Submitted Solution today . I will Attach the Java Solution in reply to this comment .
class Solution{
static int countWays(int n, String s1){
int[][][] dp=new int[n+1][n+1][3];
for(int[][]a :dp){
for(int[]aa :a){
Arrays.fill(aa ,-1);
}
}
return paranthize(s1 ,0 ,s1.length()-1 ,true ,dp);
}
static int paranthize(String s1 ,int i ,int j ,boolean isTrue ,int[][][] dp){
if(i == j){
if(isTrue){
if(s1.charAt(i)=='T'){
return 1;
}else{
return 0;
}
}else{
if(s1.charAt(i)=='F'){
return 1;
}else{
return 0;
}
}
}
if(dp[i][j][isTrue ? 1 :2]!=-1){
return dp[i][j][isTrue ? 1 :2];
}
int ways=0;
for(int k=i+1 ;k
My cpp accepted solution with runtime of 0.5
// { Driver Code Starts
// Initial Template for C++
#include
using namespace std;
// } Driver Code Ends
// User function Template for C++
int t[201][201][2];
class Solution{
public:
int countWays(int n, string s){
memset(t, -1, sizeof(t));
return solve(s, 0, n-1, true);
}
int solve(string &s, int i, int j, bool ex){
if(i > j) return 0;
int exi = (ex == true ? 1 : 0);
if(t[i][j][exi] != -1) return t[i][j][exi];
if(i == j){
if(ex){
return t[i][j][exi] = (s[i] == 'T');
}
else{
return t[i][j][exi] = (s[i] == 'F');
}
}
int ans = 0;
for(int k = i+1; k
@@nabeelmehar2984 Hey! What's the %1003 for?
Bro.. what microphone, camera and stick u use to keep in such position can you say? It's nice and interesting!! 😇
kyaa bhai hr jgh troll kr rha h tu isko 😅
backtracking and Greedy
Both map and 3d matrix will work absolutely fine but to pass all test cases use modulo in your code..
iam getting some segmentation fault 😶😶
Bro ek doubt he ki jo solve recursive calls he usme seedhe sare LT , RT , LF , RF par call kr rahe he , but hame ye check nhi krna chahiye ki wo subproblems pehle se hi t matrix me exist kr rahi he ya nahi . ( jesa optimization boolean parenth. me kiya tha ).
Please clear this doubt.
interviewbit accept nhi kr rha tha isliye thoda optimise krdiya jisse kuch fn calls na krne pade.
agar is case me bhi aisa hai toh optimise kr skte ho
bhai koi fayda ni usko check krke kyoki agar manlo LT solve ho chuki h aur humne usko call krdiya to wo bas ek extra recursion call legi or wps aa jaiga parent program mai... to usse TC pr farak ni padga na hi optimization pr.
@@lovleshbhatt7797 recursive calls are slower than if else condition so many recursive calls would be saved if you check it before and I think it's a kind of optimization otherwise interview bit wouldn't have accepted the solution
//{ Driver Code Starts
// Initial Template for C++
#include
using namespace std;
// } Driver Code Ends
// User function Template for C++
class Solution{
public:
unordered_map mp;
long long solve(string &s,int i,int j,bool istrue)
{
if(i > j)
{
return false;
}
else if(i == j)
{
if(istrue)
{
return s[i] == 'T';
}
else
{
return s[i] == 'F';
}
}
string temp = to_string(i) + ' ' +to_string(j) + ' ' + to_string(istrue);
//cout>S;
Solution ob;
cout
with the same code mine is showing TLE
map is giving tle in gfg
What is the space and time complexity for this solution?
showing TLE with map but not with 3d array plus few more optimization done in calculating lt lf rt rf as you taught in palindrome partitioning optimization.
thanks^infinity is small for you man!
well this not my real id : }
Bro can u share me the code.
@@amansinghgautam9189 did u get the code?
You can get entire solution with 3d matrix approach here:
leetcode.com/discuss/general-discussion/1279635/boolean-parenthesization-easy-c
C++ | code below
unordered_map mpp;
int solve(string s,int i,int j,bool isTrue){
if(i>j)
return false;
if(i==j){
if(isTrue==true)
return s[i]=='T';
else
return s[i]=='F';
}
string temp= to_string(i)+ " "+to_string(j)+" "+to_string(isTrue);
if(mpp.find(temp)!=mpp.end())
return mpp[temp];
int ans=0;
for(int k=i+1;k
i was thinking if one has to solve using 2d matrix only just make two 2d matrix one for true and another for flase and just have a check on the starting on istrue ? I hope this approch will work as well 😊
Yes I did it
int solve(string s, int i, int j, bool isTrue, vector& dpTrue, vector& dpFalse){
if(i>j){
return 0;
}
if(i==j){
if(isTrue == true){
return s[i]=='T';
}else if(isTrue == false){
return s[i]=='F';
}
}
if(isTrue == true && dpTrue[i][j]!=-1){
return dpTrue[i][j];
}else if(isTrue == false && dpFalse[i][j]!=-1){
return dpFalse[i][j];
}
int ans = 0;
for(int k=i+1; k
why for i>j condition, we are returning true? at that time expression can't be evaluated, so it should be returning false..
it was a silly mistake, if you look at the previous video it's written false there!
@@adarshkunwar8113 *there
@@priyanshukhullar5836 fixed it! Thx!
Very clear explanation in both part 1 and part 2. I understood everything.Thank you so much🤗