word break | Dynamic programming | geeks for geeks solution

 Given a string A and a dictionary of n words B, find out if A can be segmented into a space-separated sequence of dictionary words.

Note: From the dictionary B each word can be taken any number of times and in any order.
Example 1:

Input:
n = 12
B = { "i", "like", "sam",
"sung", "samsung", "mobile",
"ice","cream", "icecream",
"man", "go", "mango" }
A = "ilike"
Output:
1
Explanation:
The string can be segmented as "i like".

Example 2:

Input:
n = 12
B = { "i", "like", "sam",
"sung", "samsung", "mobile",
"ice","cream", "icecream", 
"man", "go", "mango" }
A = "ilikesamsung"
Output:
1
Explanation:
The string can be segmented as 
"i like samsung" or "i like sam sung".

 

Your Task:
Complete wordBreak() function which takes a string and list of strings as a parameter and returns 1 if it is possible to break words, else return 0. You don't need to read any input or print any output, it is done by driver code.

Answer : 

class Solution

{

    bool find_word(vector<string>&b , string a)

    {

        for(auto i = b.begin() ; i!= b.end() ; i++)

        {

            if(a == *i)

             return true;

        }

        return false;

    }

public:

    int wordBreak(string A, vector<string> &B) {

         

         if(A.length() == 0)

         {

             return 1;

         }

        

        for(int i =0 ; i < A.length() ; i++)

        { 

            string p = A.substr(0 , i+1);

            if(find_word(B, p))

               {

                  if(wordBreak(A.substr(i+1) , B))

                    return 1;

               }

            

        }

        return 0;

    }

};

References : https://practice.geeksforgeeks.org/problems/word-break1352/1#