Word break Problem

#1

@mr.encoder can you show dry run how the recursion states works? for this problem?
this is code–> i cannot understand

    class Solution {
    public:
        unordered_map<string,bool> m;
        bool ispossible(string s,int start){
            if(start==s.length()){
                return true;
            }
            for(int i=start+1;i<=s.length();i++){
                string word=s.substr(start,i-start);
                if(m.count(word)!=0 and ispossible(s,i)){
                    return true;
                }
            }
            return false;
        }
        bool wordBreak(string s, vector<string>& wordDict) {
            for(int i=0;i<wordDict.size();i++){
                m[wordDict[i]]=true;
            }
            return ispossible(s,0);
        }
    };

question–>

#2

You want me to show you recursive calls in ispossible function?

#3

yes i cannot how recursion works when there is for loop in it

#4

yes ispossible function only

#5

here is the reference code–>

#6

Bro give me one code. I was halfway . Have to start again now :joy:. Is this code fine? If yes then please wait as i am building recursion tree.

#7

this is code from which i am learning this is code bro the github link

#8

Okay now wait i am building it. Give me some time i will post the pic here only

#9

I have tried but have failed in drawing a neat recursive tree. Though attaching my best try hope it will help you for sure

image
image1000×543 167 KB

We are doing nothing but calling the remaining part of the string and to clear it more the recursive call will be made first instead executing complete for loop.

#12

since there will be multiple break points in the words we use recursion to see that right? ohh that’s why question name is also word break

#13

Tum mujhe recursive call explain kr rhe ho? Ya doubt puch rhe ho mujhe smjh ni aa rha LOL. SO if there is any doubt then do ask

#14

when the substring is not present in the hashmap the recursive call will not be executed ,then why you have drawn in recursion tree?

#15

substring is not present in the hashmap then we will do recursive call but if it’s present only then we won’t do it in recursive call.

#16

okay that’s what i wanted to ask thanks

#17

Have done this recursive call where my s = "abcd" and wordDict = ["a", "b", "c", "bc", "ab", "abc"]
Try to dry run on your own and for better explanation you can see videos too on youtube. If you like my explanation do give hearts and rating.

1 Like
#18

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#19

the recursive you have drawn in pencil will not be executed ,now only i understand.

#20

Yes this is what i mean one with pencil won’t but with pen will.