Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Approach
2.1.
Implementation in C++
2.1.1.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
What is dfs?
3.2.
What is an application of recursion?
3.3.
What is time complexity?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Word Break Problem using Backtracking

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM
Backtracking and Recursion

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;
}

 

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²).

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What is dfs?

Dfs or depth-first search is an algorithm for traversing a graph. 

What is an application of recursion?

Many well-known sorting algorithms (Quick sort, Merge sort, etc.) use recursion.

What is time complexity?

The time complexity of an algorithm can be defined as the time taken by the computer to run an algorithm.

Conclusion

This article discussed the word break problem using backtracking and recursion. We hope you have gained a better understanding of the solution to this problem and, now it is your responsibility to solve the problem and try some new and different approaches to this problem. 

Recommended Problems:


Recommended Readings:


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!

Previous article
Sudoku Solver
Next article
Tug Of War
Live masterclass