Home » Interview coding problems/challenges

Word Break Problem

In this article, we are going to learn the solution to the word break problem. This is about how we split a string into a meaningful word? This problem has been featured in Amazon interview rounds. Submitted by Souvik Saha, on May 08, 2019

Problem Statement:

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) 

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