fork(99) download 
  1. // A recursive program to print all possible partitions of a given string
  2. // into dictionary words
  3. #include <iostream>
  4. using namespace std;
  5.  
  6. /* A utility function to check whether a word is present in dictionary or not.
  7.   An array of strings is used for dictionary.  Using array of strings for
  8.   dictionary is definitely not a good idea. We have used for simplicity of
  9.   the program*/
  10. int dictionaryContains(string word)
  11. {
  12.     string dictionary[] = {"mobile","samsung","sam","sung","man","mango",
  13.                            "icecream","and","go","i","love","ice","cream"};
  14.     int size = sizeof(dictionary)/sizeof(dictionary[0]);
  15.     for (int i = 0; i < size; i++)
  16.         if (dictionary[i].compare(word) == 0)
  17.            return true;
  18.     return false;
  19. }
  20.  
  21. //prototype of wordBreakUtil
  22. void wordBreakUtil(string str, int size, string result);
  23.  
  24. void wordBreak(string str)
  25. {
  26.     //last argument is prefix
  27.     wordBreakUtil(str, str.size(), "");
  28. }
  29.  
  30. // result store the current prefix with spaces between words
  31. void wordBreakUtil(string str, int size, string result)
  32. {
  33.     //Process all prefixes one by one
  34.     for (int i=1; i<=size; i++)
  35.     {
  36.         //extract substring from 0 to i in prefix
  37.         string prefix = str.substr(0, i);
  38.  
  39.         // if dictionary conatins this prefix, then we check
  40.         // for remaining string. Otherwise we ignore this prefix
  41.         // (there is no else for this if) and try next
  42.         if (dictionaryContains(prefix))
  43.         {
  44.             // if no more elements are there, print it
  45.             if (i == size)
  46.             {
  47.                 // add this element to previous prefix
  48.                 result += prefix;
  49.                 cout << result << endl; //print result
  50.                 return;
  51.             }
  52.             wordBreakUtil(str.substr(i, size-i), size-i, result+prefix+" ");
  53.         }
  54.     }      //end for
  55. }//end function
  56.  
  57. int main()
  58. {
  59.     cout << "First Test:\n";
  60.     wordBreak("iloveicecreamandmango");
  61.  
  62.     cout << "\n\nSecond Test:\n";
  63.     wordBreak("ilovesamsungmobile");
  64.     return 0;
  65. }
  66.  
Success #stdin #stdout 0s 2988KB
comments (?)
stdin 
Standard input is empty
stdout 
First Test:
i love ice cream and man go
i love ice cream and mango
i love icecream and man go
i love icecream and mango


Second Test:
i love sam sung mobile
i love samsung mobile
https://ideone.com/53LMkr
language:
C++14 (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!