Word Break [ IBM – Google ]

Problem:

Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words. See following examples for more details. Consider the following dictionary
{ i, like, sam, sung, samsung, mobile, ice,cream, icecream, man, go, mango}

Input:  ilike
Output: Yes
The string can be segmented as “i like”.

Input:  ilikesamsung
Output: Yes
The string can be segmented as “i like samsung” or “i like sam sung”.

Problem Link

#include <stdio.h>
#include <iostream>
#include <string>
#include <cstring>

/*
12
mobile samsung sam sung man mango icecream and go i like ice cream
ilike
*/

using namespace std;
string dic[18];
bool dp[1005];
int n;
bool wordFound(string s)
{
    for(int i=0;i<n;i++)
        if(dic[i].compare(s)==0)
            return 1;
    return 0;
}
bool wordbreak(string str)
{
    int sz=str.size();
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=sz;i++)
    {
        if(dp[i]==0 && wordFound(str.substr(0,i))==1)
        dp[i]=1;
        
        if(dp[i]==1)
        {
            if(i==sz)
            return 1;
            for(int j=i+1;j<=sz;j++)
            {
                if(dp[j]==0 && wordFound(str.substr(i,j-i))==1)
                dp[j]=1;
                if(j==sz && dp[j]==1)
                return 1;
            }
        }
    }
    //cout<<dp[sz-1]<<"\n";
    return 0;
}
int main() {
	//code
	int t;
	string str;
	scanf("%d",&t);
	while(t--)
	{
	    scanf("%d",&n);
	    for(int i=0;i<n;i++)
	    {
	        cin>>dic[i];
	    }
	    cin>>str;
	    cout<<wordbreak(str)<<"\n";
	}
	return 0;
}