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;
}

```
darkmode