Word Break Problem using Backtracking

Introduction

So, we have to solve the word break problem using backtracking and recursion, we are given a correct sentence without any spaces between the words. We are also given a dictionary of valid English words; we have to find all the possible ways to break the sentence into individual dictionary words.

So before we deep dive into the solution to this problem, we should first look at some examples to understand the problem better.

Sample Examples

Consider the following dictionary

{ apple, devices, love, I, have, the, new, spider-man, movie, watched, in, theater }

Input: “Iloveappledevices”

Output: I love apple devices

Input: “Ihavewatchedthenewspider-manmovieinthetheater”

Output: I have watched the new spider-man movie in the theater

Also see, Data Structures

Approach

1. So the approach to solving this word break problem using backtracking is that we will start scanning the sentence from the left. As we find a valid word, we will check whether the rest of the sentence makes valid words because there can be a situation where the first word we found from the left side of the string can leave a remaining portion that cannot be separated into meaningful words. 
2. So, in that case, we will come back and leave the currently found word, and we will keep on searching for the next word. And this process is recursive because we need to find out whether the right portion is separable or not.
3.  To keep track of the found words, we will use a stack, and whenever the right portion of the string does not make any valid words, we will pop the top string from the stack and continue finding more words.

Also see, Backtracking and Recursion

Implementation in C++

// C++ code for word break problem using backtracking
#include <bits/stdc++.h>
using namespace std;

// To check if the word is present in the dictionary
// or not we have used an array of strings
int ifdictionaryContains(string &word)
{
    string dictionaryWords[] = {"apple", "devices", "love", "I", "have", "the", "new", "spider-man", "movie", "watched", "in", "theater"};
    int n = sizeof(dictionaryWords) / sizeof(dictionaryWords[0]);
    for (int i = 0; i < n; i++)
        if (dictionaryWords[i].compare(word) == 0)
            return true;
    return false;
}

// Prototype of wordBreakUtil
void wordBreakFunction(string str, int size, string answer);

// to print all possible words of the string
void wordBreak(string str)
{
    wordBreakFunction(str, str.size(), "");
}

// to store the current prefix with spaces between words
void wordBreakFunction(string str, int n, string answer)
{
    // to check every prefix one by one
    for (int i = 1; i <= n; i++)
    {
        // storing the substring from 0 to i in prefix
        string prefix = str.substr(0, i);

        // if dictionary has this prefix then we will
        // check for the remaining string. Otherwise we will
        // ignore this prefix
        if (ifdictionaryContains(prefix))
        {
            // if no more elements are there, then we will print it
            if (i == n)
            {
                // add this element to answer
                answer += prefix;
                cout << answer << endl;
                return;
            }
            wordBreakFunction(str.substr(i, n - i), n - i, answer + prefix + " ");
        }
    }
}

// Driver Code
int main()
{
    cout<<"Input: Ihavewatchedthenewspider-manmovieinthetheater"<<endl;

    cout<<"Output: ";

    // Function call
    wordBreak("Ihavewatchedthenewspider-manmovieinthetheater");

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Input: Ihavewatchedthenewspider-manmovieinthetheater

Output: I have watched the new spider-man movie in the theater

Complexity Analysis

Time Complexity:  O( 2ⁿ)

Since there are 2ⁿ combinations in the worst-case, the time complexity of the above approach is O(2ⁿ).

Space Complexity: O(n²)

The space complexity is O(n²).