Strings: Word Break Problem

Problem Statement:

You are given a word and series of dictionary.

You need to check if the word can be broken down into multiple words that are present in the dictionary

Example

Dictionary

{ i, like, mobile, ice, cream, mango}

Input: ilike
Output: Yes 
The string can be separated as "i like".

Solution

The solution is very simple.
We shall user DP to solve this problem.

We shall create a Boolean DP array of size (length+1).
Then we shall set dp[i] is set to true if it is a valid word.
Then if dp[j] is true, then we check if the substring is present in the dictionary.

Example:
———–

Dict = {"hi", "hello"} ;   
string = "hihello" ;


i = 1
 j = 0
 j is true substring = h

i = 2
 j = 1
 j = 0
 j [0] is true substring = hi

i = 3
 j = 2
  j [2] is true substring = h
 j = 1
 j = 0
  j [0] is true substring = hih

i = 4
 j = 3
 j = 2
  j [2] is true substring = he
 j = 1
 j = 0
  j [0] is true substring = hihe

i = 5
 j = 4
 j = 3
 j = 2
  j [2] is true substring = hel
 j = 1
 j = 0
  j [0] is true substring = hihel

i = 6
 j = 5
 j = 4
 j = 3
 j = 2
  j [2] is true substring = hell
 j = 1
 j = 0
  j [0] is true substring = hihell

i = 7
 j = 6
 j = 5
 j = 4
 j = 3
 j = 2
  j [2] is true substring = hello

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_set>
#include <queue>

using namespace std;

bool wordBreak(string s, unordered_set<string> &dict) 
{
     if(dict.size()==0) return false;
     
     vector<bool> dp(s.size()+1, false);
     dp[0] = true;
     
     for(int i=1;i<=s.size();i++)
     {
         for(int j=i-1;j>=0;j--)
         {
             if(dp[j])
             {
                 string word = s.substr(j,i-j);
                 if(dict.find(word)!= dict.end())
                 {
                     dp[i]=true;
                     break; 
                 }
             }
         }
     }
     
     return dp[s.size()];
 }
int main() 
{ 
    unordered_set <string> dict ; 
  
    dict.insert("hi") ; 
    dict.insert("hello") ;   
    string s = "hihello" ;

    if(wordBreak(s, dict))
    {
      cout<<"True"<<endl;
    } else {
      cout<<"False"<<endl;
    }

    return 0; 
} 

Output:

True