Word break problem -dynamic programming

Given a non-empty string and a dictionary containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.

Example 1:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
             Note that you are allowed to reuse a dictionary word.

Example 2:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false





method 1: recursive solution

t is the no. of test cases, d is the dictionary, and s is the given string

c++ implementation:

#include<bits/stdc++.h>
using namespace std;

int rec(string s,set<string>d)
{
	if(s=="")
	return 1;

	for(int i=1;i<=s.length();i++)
	{
		if(d.count(s.substr(0,i)) && rec(s.substr(i,s.length()),d) )
		return 1;
	}
	return 0;
}
int main()
{
	int t; cin>>t;
	while(t--)
	{
		int n ; cin>>n;
		set<string>d;
		for(int i=0;i<n;i++)
		{
			string b;
			cin>>b;
			d.insert(b);
		}
        
		
		string s;cin>>s;
		cout<<rec(s,d)<<endl;
		
	}
}

method 2:dynamic programming .

t is the no.of test cases.

c++ implementation:

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main() { int t; cin>>t ;
while(t--)
{ int n; cin>>n;
 set<string>dict;

for(int i=0;i<n;i++)
{
    string k;
    cin>>k;
    dict.insert(k);
}

string s;
cin>>s;
int m=s.size();

bool dp[m+1];
for(int i=1;i<m+1;i++)
dp[i]=0;

dp[0]=1;

  for(int l=1;l<=m;l++)
  {  
           for(int h=0;h<l;h++)
            {   
                string a=s.substr(h,l-h);
                if(dict.count(a)&& dp[h]==1)
                {
                    dp[l]=1; 
                    break;
                }
            }
 
  }

cout<<dp[m]<<endl;
}
 //code
 return 0;
}