We want to devise a dynamic programming solution to the following problem: there

Question

We want to devise a dynamic programming solution to the following problem: there is a string of characters which might have been a sequence of words with all the spaces removed, and we want to find a way, if any, in which to insert spaces that separate valid English words.

1 Description We want to devise a dynamic programming solution to the following problem: there is a string of characters which might have been a sequence of words with all the spaces removed, and we want to find a way, if any, in which to insert spaces that separate valid English words. For example, youth event could be from "the you the vent" the youth event" or "they out he vent". If they the input is theeaglehaslande, then there's no such way. Your task is to implement a dynamic programming solution in two separate ways iterative bottom-up version recursive memoized version Assume that the original sequence of words had no other punctuation (such as periods), no capital letters, and no proper names all the words will be available in a dictionary file that will be provided to you Let the input string be z r122...an. We define the subproblem splits (i) as that of determining whether it is possible to correctly add spaces to rizi+1...acm. Let dict(a) be the function that will look up a provided word in the dictionary, and return true iff the word w is in it. A recurrence relation for split is given below: if i n 1 true split(i) Obviously, split(i) only finds out whether there's a sequence of valid words or not. Your pro- grama must also find at least one such sequence. The program will read a text file from standard input. For example, if you have a Java class named dynProg, the command java dynProg insample.txt is what you would use to run your program. The name of the dictionary file should be hardwired in the code. We will be testing your program on a file named "diction 10k.txt" 2 Sample Input The first line of input is an integer C. This is followed by C lines, each containing a single string, representing a phrase to be tested

Explanation / Answer

// A recursive program to test whether a given string can be segmented into
// space separated words in dictionary
#include <iostream>
using namespace std;

/* A utility function to check whether a word is present in dictionary or not.
An array of strings is used for dictionary. Using array of strings for
dictionary is definitely not a good idea. We have used for simplicity of
the program*/
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;
}

// returns true if string can be segmented into space separated
// words, otherwise returns false
bool wordBreak(string str)
{
int size = str.size();

// Base case
if (size == 0) return true;

// Try all prefixes of lengths from 1 to size
for (int i=1; i<=size; i++)
{
// The parameter for dictionaryContains is str.substr(0, i)
// str.substr(0, i) which is prefix (of input string) of
// length 'i'. We first check whether current prefix is in
// dictionary. Then we recursively check for remaining string
// str.substr(i, size-i) which is suffix of length size-i
if (dictionaryContains( str.substr(0, i) ) &&
wordBreak( str.substr(i, size-i) ))
return true;
}

// If we have tried all prefixes and none of them worked
return false;
}

// Driver program to test above functions
int main()
{
wordBreak("ilikesamsung")? cout <<"Yes ": cout << "No ";
wordBreak("iiiiiiii")? cout <<"Yes ": cout << "No ";
wordBreak("")? cout <<"Yes ": cout << "No ";
wordBreak("ilikelikeimangoiii")? cout <<"Yes ": cout << "No ";
wordBreak("samsungandmango")? cout <<"Yes ": cout << "No ";
wordBreak("samsungandmangok")? cout <<"Yes ": cout << "No ";
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.