Word Break

/***

Word Break Problem

***/

#include<iostream>

#include<string>

#include <vector>

using namespace std;

#define MAX_LEN 8

bool dictionaryContains(string word)

{

       string dictionary[] = {"mobile","samsung","sam","sung","man","mango",

              "icecream","and","go","i","like","ice","cream"};

       int size = sizeof(dictionary)/sizeof(dictionary[0]);

       for (int i = 0; i < size; i++)

              if (dictionary[i].compare(word) == 0)

                     return true;

       return false;

}

void split_word(string s, int index, vector<string> words, vector<vector<string>> *w) {

       //base case

       if(index == s.size()) {

              w->push_back(words);

              return;

       }

       if (index > s.size()) return;

       string str = "";

       for(int i = 0; i<MAX_LEN && i+index<s.size(); i++) {

              str.push_back(s[i+index]);

              if(dictionaryContains(str)) {

                     words.push_back(str);

                     split_word(s, index+i+1, words, w);

                     words.pop_back();

              }

       }

}

void main() {

       string s = "ilikesamsung";

       vector<vector<string>> sens;

       vector<string> words;

       split_word(s, 0, words, &sens);

       for (int i = 0; i<sens.size(); i++)

       {

              for(int j = 0; j<sens[i].size(); j++)

                     cout<<sens[i][j]<<" ";

              cout<<endl;

       }

}