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


lets use dynamic programming to solve this question:
c++ implementation:

t is the no.of test cases:

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

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

darkmode