Word Break Problem in C++

Hi guys, today we will try to solve Word Break Problem in C++.

It is one of the most asked problems in placement interviews.

I would recommend you to please study the topic recursion before moving to this problem because recursion is the main thing, we will be using in this program.

There are some examples which will help you to know recursion better:

C++: Word Break Problem

So let me first tell you the aim of the problem.

In this problem, we have an array of words and the user needs to enter a string. The program should display yes/no if that string can be break into space-separated words present in the array.

Let us take an example that we have an array consisting of 2 words key and board. If the user enters the string keyboard, it should display yes because the keyboard can be broken into key-board and both the words are present in the array.

Solution

So now let us move to the solution.

This problem may have various solutions but I am using the concept of recursion to solve this problem.

Here is the code for the above problem:

#include <iostream>
using namespace std; 
int check(string var) 
{ 
    string array[] = {"mobile","microwave","television","refrigerator","mob","vision","wave","i","use","ac","fridge"}; 
    int size = sizeof(array)/sizeof(array[0]); 
    for (int j = 0; j < size; j++) 
        if (array[j].compare(var) == 0) 
           return true; 
    return false; 
} 
bool divide(string ch) 
{ 
    int size = ch.size(); 
    if (size == 0)  
        return true; 
    for (int i=1; i<=size;i++) 
    { 
        if (check(ch.substr(0,i)) && divide(ch.substr(i,size-i))) 
            return true; 
    } 
    return false; 
} 
int main() 
{ 
    string ch;
    cout<<"enter string\n";
    cin>>ch;
    if(divide(ch))
        cout<<"yes";
    else
        cout<<"no";
    return 0; 
}

The logic behind the code is that we will break the string into 2 parts and check whether the first part is present in the array or not and recursively break the second part to check the same. This process continues until the complete string gets checked.

The check function will check whether the string is present in the array or not. If it finds the string in the array, then it returns true else returns false.

Initially, the input string is passed in divide function where it gets broken into 2 parts i.e. first part containing the first letter of the string, and the second part contains the rest of the string.
It will then pass the first part to check function to check whether the array contains it or not. And, if the array does not contain the first part, the string will be broken again but this time the first part contains the first 2 letters of the string, and rest will be in the second part and the same process continues until the complete string gets checked.

Now let us see what we get for an input:

enter string
mobvision

So the output for the above input will be:

yes

Let us take another string as an input:

enter string
iuseac

So its output will be:

yes

I tried to explain this problem in the simplest way, so I hope you guys would understand it.

Thank You

Leave a Reply

Your email address will not be published. Required fields are marked *