#include <iostream>
#include <string.h>
using namespace std;
int 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;
}
bool wordBreak(string str)
{
int size = str.size();
if (size == 0) return true;
bool wb[size+1];
memset(wb, 0, sizeof(wb));
for (int i=1; i<=size; i++)
{
if (wb[i] == false && dictionaryContains( str.substr(0, i) ))
wb[i] = true;
if (wb[i] == true)
{
if (i == size)
return true;
for (int j = i+1; j <= size; j++)
{
if (wb[j] == false && dictionaryContains( str.substr(i, j-i) ))
wb[j] = true;
for (int i = 1; i <= size; i++)
cout << " " << wb[i];
if (j == size && wb[j] == true)
return true;
}
}
}
for (int i = 1; i <= size; i++)
cout << " " << wb[i];
return false;
}
int main()
{
wordBreak("ilikesamsung")? cout <<"Yes\n": cout << "No\n";
wordBreak("iiiiiiii")? cout <<"Yes\n": cout << "No\n";
wordBreak("")? cout <<"Yes\n": cout << "No\n";
wordBreak("ilikelikeimangoiii")? cout <<"Yes\n": cout << "No\n";
wordBreak("samsungandmango")? cout <<"Yes\n": cout << "No\n";
wordBreak("samsungandmangok")? cout <<"Yes\n": cout << "No\n";
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3RyaW5nLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmludCBkaWN0aW9uYXJ5Q29udGFpbnMoc3RyaW5nIHdvcmQpCnsKICAgIHN0cmluZyBkaWN0aW9uYXJ5W10gPSB7Im1vYmlsZSIsInNhbXN1bmciLCJzYW0iLCJzdW5nIiwibWFuIiwibWFuZ28iLAogICAgICAgICAgICAgICAgICAgICAgICAgICAiaWNlY3JlYW0iLCJhbmQiLCJnbyIsImkiLCJsaWtlIiwiaWNlIiwiY3JlYW0ifTsKICAgIGludCBzaXplID0gc2l6ZW9mKGRpY3Rpb25hcnkpL3NpemVvZihkaWN0aW9uYXJ5WzBdKTsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgc2l6ZTsgaSsrKQogICAgICAgIGlmIChkaWN0aW9uYXJ5W2ldLmNvbXBhcmUod29yZCkgPT0gMCkKICAgICAgICAgICByZXR1cm4gdHJ1ZTsKICAgIHJldHVybiBmYWxzZTsKfQpib29sIHdvcmRCcmVhayhzdHJpbmcgc3RyKQp7CiAgICBpbnQgc2l6ZSA9IHN0ci5zaXplKCk7CiAgICBpZiAoc2l6ZSA9PSAwKSAgIHJldHVybiB0cnVlOwogICAgYm9vbCB3YltzaXplKzFdOwogICAgbWVtc2V0KHdiLCAwLCBzaXplb2Yod2IpKTsgCiAgICBmb3IgKGludCBpPTE7IGk8PXNpemU7IGkrKykKICAgIHsKICAgICAgICBpZiAod2JbaV0gPT0gZmFsc2UgJiYgZGljdGlvbmFyeUNvbnRhaW5zKCBzdHIuc3Vic3RyKDAsIGkpICkpCiAgICAgICAgICAgIHdiW2ldID0gdHJ1ZTsKICAgICAgICBpZiAod2JbaV0gPT0gdHJ1ZSkKICAgICAgICB7CiAgICAgICAgICAgIGlmIChpID09IHNpemUpCiAgICAgICAgICAgICAgICByZXR1cm4gdHJ1ZTsKICAgICAgICAgICAgZm9yIChpbnQgaiA9IGkrMTsgaiA8PSBzaXplOyBqKyspCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGlmICh3YltqXSA9PSBmYWxzZSAmJiBkaWN0aW9uYXJ5Q29udGFpbnMoIHN0ci5zdWJzdHIoaSwgai1pKSApKQogICAgICAgICAgICAgICAgICAgIHdiW2pdID0gdHJ1ZTsKCQkgICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IHNpemU7IGkrKykKICAgICAgICBjb3V0IDw8ICIgIiA8PCB3YltpXTsgCiAgICAgICAgICAgICAgICBpZiAoaiA9PSBzaXplICYmIHdiW2pdID09IHRydWUpCiAgICAgICAgICAgICAgICAgICAgcmV0dXJuIHRydWU7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gc2l6ZTsgaSsrKQogICAgICAgIGNvdXQgPDwgIiAiIDw8IHdiW2ldOyAKICAgIHJldHVybiBmYWxzZTsKfQppbnQgbWFpbigpCnsKICAgIHdvcmRCcmVhaygiaWxpa2VzYW1zdW5nIik/IGNvdXQgPDwiWWVzXG4iOiBjb3V0IDw8ICJOb1xuIjsKICAgIHdvcmRCcmVhaygiaWlpaWlpaWkiKT8gY291dCA8PCJZZXNcbiI6IGNvdXQgPDwgIk5vXG4iOwogICAgd29yZEJyZWFrKCIiKT8gY291dCA8PCJZZXNcbiI6IGNvdXQgPDwgIk5vXG4iOwogICAgd29yZEJyZWFrKCJpbGlrZWxpa2VpbWFuZ29paWkiKT8gY291dCA8PCJZZXNcbiI6IGNvdXQgPDwgIk5vXG4iOwogICAgd29yZEJyZWFrKCJzYW1zdW5nYW5kbWFuZ28iKT8gY291dCA8PCJZZXNcbiI6IGNvdXQgPDwgIk5vXG4iOwogICAgd29yZEJyZWFrKCJzYW1zdW5nYW5kbWFuZ29rIik/IGNvdXQgPDwiWWVzXG4iOiBjb3V0IDw8ICJOb1xuIjsKICAgIHJldHVybiAwOwp9