Q:

Given a dictionary, you have to split a given string into meaningful words

mahmoud2506
Save to bookmark
|
2022-04-30
|
  271 
0

Word Break Problem

Given a dictionary, you have to split a given string into meaningful words.

Example:

    Case-I:
    If the dictionary contain the words: 
    {"like", "i" , "ice" , "cream", "is"};
    Input : "ilikeicecream"
    Output: "i like ice cream"

    Case-II:
    If the dictionary contain the words: 
    {"like", "i" , "ice" , "cream", "is"}
    Input: "ilikeeicecream"
    Output: False 
    (There is no combination possibleout from the dictionary)
C++ programming, Interview questions, C++ programming Interview-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-04-30
need an explanation for this answer? contact us directly to get an explanation for this answer

Algorithm:

We solve the problem using dynamic programming. The problem contains two parts one is detecting the words and the other one is retrieving the words.

Case-I

  1. We take a Boolean array of length the same as the length of the string and initialize it with false.
  2. We take a vector and initialize it with -1.
  3. We start comparing the string from position 0 and increment the length at each time by one.
  4. Whenever we find a meaningful word we push_back() that index into the vector and make that index in the boolean array true.
  5. After inserting the index then we start checking the next word from that index and also the previous index.
  6. Repeat step 2 to step 5 until we traverse the whole string.
  7. If the (length -1) index in the boolean array is true then we separate the string otherwise we don't.

Case-II

  1. We take the sub-string from the last element of the vector to the last of the string and check to the dictionary.
  2. If found then next time last will be the last element of the vector.
  3. If not found then only go to the next to last element of that vector.
  4. Repeat the process until we go to the first element of the vector.
 

C++ Implementation for word break problem

#include <bits/stdc++.h>
using namespace std;

bool dictionary_contain(string str, string* dictionary, int num)
{
    for (int i = 0; i < num; i++) {
        //if any word match with the word
        //in the dictionary then break the loop
        if (dictionary[i].compare(str) == 0)
            return true;
    }
    return false;
}

bool word_split(string s, vector<int>& ind, string* dictionary, int num)
{
    int len = s.size();
    //if the string is empty then it true
    if (len == 0)
        return true;
    //decleare the boolean array of length
    //same as the string
    vector<int> dp(len, 0);
    ind.push_back(-1);
    for (int i = 0; i < len; i++) {
        int size = ind.size();
        int tag = 0;
        for (int j = size - 1; j >= 0; j--) {
            string sb = s.substr(ind[j] + 1, i - ind[j]);
            if (dictionary_contain(sb, dictionary, num)) {
                tag = 1;
                break;
            }
        }
        if (tag) {
            dp[i] = 1;
            ind.push_back(i);
        }
    }
    return dp[len - 1];
}

int main()
{
    string s = "ilikeicecream";
    //contains of the dictionary
    string dictionary[] = { "i", "like", "ice", "cream", "is", "cool" };
    int num = sizeof(dictionary) / sizeof(dictionary[0]);
    vector<int> ind;
    if (word_split(s, ind, dictionary, num)) {
        cout << "True" << endl;
        vector<int>::iterator it;
        string str = "";
        int last = s.size();
        int len = 0;
        int* arr = new int[ind.size()];
        for (it = ind.begin(); it != ind.end(); it++) {
            arr[len++] = *it;
        }
        list<string> word;
        for (int i = len - 1; i >= 0; i--) {
            str = s.substr(arr[i] + 1, last - arr[i]);
            if (dictionary_contain(str, dictionary, num)) {
                last = arr[i];
                word.push_front(str);
                str = "";
            }
        }
        list<string>::iterator i;
        for (i = word.begin(); i != word.end(); i++) {
            cout << *i << " ";
        }
    }
    else {
        cout << "false" << endl;
    }
    return 0;
}

Output

True
i like ice cream

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

interview C++ coding problems/challenges | dynamic programming
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
There are N friends, each one of them can remain s... >>
<< Given a value V, if we want to make change for V c...