fork download
copy 
  1. #include <iostream>
  2. #include <string.h>
  3. using namespace std;
  4.  
  5. /* A utility function to check whether a word is present in dictionary or not.
  6.   An array of strings is used for dictionary.  Using array of strings for
  7.   dictionary is definitely not a good idea. We have used for simplicity of
  8.   the program*/
  9. int dictionaryContains(string word)
  10. {
  11.     string dictionary[] = {"i", "like", "go", "hired", "gohired", "site", "sweet","fruit", "man", "go", "mango"};
  12.     int size = sizeof(dictionary)/sizeof(dictionary[0]);
  13.     for (int i = 0; i < size; i++)
  14.         if (dictionary[i].compare(word) == 0)
  15.            return true;
  16.     return false;
  17. }
  18.  
  19. // Returns true if string can be segmented into space separated
  20. // words, otherwise returns false
  21. bool wordBreak(string str)
  22. {
  23.     int size = str.size();
  24.     if (size == 0)   return true;
  25.  
  26.     // Create the DP table to store results of subroblems. The value wb[i]
  27.     // will be true if str[0..i-1] can be segmented into dictionary words,
  28.     // otherwise false.
  29.     bool wb[size+1];
  30.     memset(wb, 0, sizeof(wb)); // Initialize all values as false.
  31.  
  32.     for (int i=1; i<=size; i++)
  33.     {
  34.         // if wb[i] is false, then check if current prefix can make it true.
  35.         // Current prefix is "str.substr(0, i)"
  36.         if (wb[i] == false && dictionaryContains( str.substr(0, i) )){
  37.             wb[i] = true;
  38.         	//cout<<str.substr(0, i)<<wb[i]<<"\n";
  39.         }
  40.         // wb[i] is true, then check for all substrings starting from
  41.         // (i+1)th character and store their results.
  42.         if (wb[i] == true)
  43.         {
  44.             // If we reached the last prefix
  45.             if (i == size)
  46.                 return true;
  47.  
  48.             for (int j = i+1; j <= size; j++)
  49.             {
  50.                 // Update wb[j] if it is false and can be updated
  51.                 // Note the parameter passed to dictionaryContains() is
  52.                 // substring starting from index 'i' and length 'j-i'
  53.                 if (wb[j] == false && dictionaryContains( str.substr(i, j-i) )){
  54.                     wb[j] = true;
  55.                 	//cout<<str.substr(0, i)<<wb[i]<<"\n";
  56.                 }
  57.  
  58.                 // If we reached the last character
  59.                 if (j == size && wb[j] == true)
  60.                     return true;
  61.             }
  62.         }
  63.     }
  64.  
  65.     for (int i = 1; i <= size; i++)
  66.         cout<<str.substr(0, i) << "-" <<wb[i]<<"\n";
  67.  
  68.     // If we have tried all prefixes and none of them worked
  69.     return false;
  70. }
  71.  
  72. // Driver program to test above functions
  73. int main()
  74. {
  75.     wordBreak("ilikemngo")? cout <<"Yes\n": cout << "No\n";
  76.     //wordBreak("iiiiiiii")? cout <<"Yes\n": cout << "No\n";
  77.     //wordBreak("")? cout <<"Yes\n": cout << "No\n";
  78.     //wordBreak("ilikelikeimangoiii")? cout <<"Yes\n": cout << "No\n";
  79.     //wordBreak("samsungandmango")? cout <<"Yes\n": cout << "No\n";
  80.     //wordBreak("samsungandmangok")? cout <<"Yes\n": cout << "No\n";
  81.     return 0;
  82. }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
i-1
il-0
ili-0
ilik-0
ilike-1
ilikem-0
ilikemn-0
ilikemng-0
ilikemngo-0
No
https://ideone.com/rvQZdI
wordbreak-old
language:
C++14 (gcc 8.3)
created:
9 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!