• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Word Break Problem

December 30, 2014 by Dhaval Dave

Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words. See following examples for more details.
This is a famous Google interview question, also being asked by many other companies now a days.Consider the following dictionary 
{ i, like, go, hired, gohired, site, sweet,fruit, man, go, mango}

Input:  ilike
Output: Yes 
The string can be segmented as “i like”.

Input:  ilikemango
Output: Yes
The string can be segmented as “i like mango” or “i like man go”.
Recursive implementation:Very easy method to keep dictionary in Hash.
Recursively traverse each substring and find whether dictionary contains it or not
example :

SubString : i , restString :likemango
for likemango
SubString : l, restString :ikemango

i-likemango
l-ikemango
li-kemango
lik-emango
like-mango
m-ango
ma-ango
man-go
g-o
go-

Finally as for I , Like and Mango , it returns true, it can will finally result true.

Code :

#include <iostream>
using namespace std;

int dictionaryContains(string word)
{
    string dictionary[] = {“i”, “like”, “go”, “hired”, “gohired”, “site”, “sweet”,”fruit”, “man”, “go”, “mango”};
    int size = sizeof(dictionary)/sizeof(dictionary[0]);
    for (int i = 0; i < size; i++)
        if (dictionary[i].compare(word) == 0)
           return true;
    return false;
}
bool wordBreak(string str)
{
    int size = str.size();
    if (size == 0)  return true;
    for (int i=1; i<=size; i++)
    {
    cout << str.substr(0, i) <<“-” <<str.substr(i, size-i)<<“n”;
        if (dictionaryContains( str.substr(0, i) ) &&
            wordBreak( str.substr(i, size-i) ))
            return true;
    }
    return false;
}

// Driver program to test above functions
int main()
{
    wordBreak(“ilikemango”)? cout <<“Yesn”: cout << “Non”;
    return 0;
}

Working Code : http://ideone.com/rGnFmp

As this Approach can be done with Recursive way, IT can be done with Dynamic Programming..
W’ll Put Dynamic Programming solution later..

Now lets see when We input String  ilikemngo What can be output trace?

 
i-likemngo
l-ikemngo
li-kemngo
lik-emngo
like-mngo
m-ngo
mn-go
mng-o
mngo-
likem-ngo
likemn-go
likemng-o
likemngo-
il-ikemngo
ili-kemngo
ilik-emngo
ilike-mngo
ilikem-ngo
ilikemn-go
ilikemng-o
ilikemngo-

Hear we have found that “ilike” can be created in sentence, then once “mngo” iteration completes, we again check for likemngo, and ilikemango …. as we can see in output trace.

So in order to reduce recursion and re-computation we can store required output.
that can be done with the help of Dynamic Programming.

Now if What we can store and how to proceed

We need to store information in order to reduce computation of substring can be broken into sentence or not… so
we can store like

i – TRUE
il – False
ili – False
ilik – False
ilike – TRUE
.
.
. and so on.
So we can store such values in a Array Arr[i], which will store the value 1 if string [0 .. i] can form a sentence.

#include <iostream>
#include <string.h>
using namespace std;
int dictionaryContains(string word)
{
    string dictionary[] = {“i”, “like”, “go”, “hired”, “gohired”, “site”, “sweet”,”fruit”, “man”, “go”, “mango”};
    int size = sizeof(dictionary)/sizeof(dictionary[0]);
    for (int i = 0; i < size; i++)
        if (dictionary[i].compare(word) == 0)
           return true;
    return false;
}
bool wordBreak(string str)
{
    int size = str.size();
    if (size == 0)   return true;

    bool wb[size+1];
    memset(wb, 0, sizeof(wb)); // Initialize all values as false.

    for (int i=1; i<=size; i++)
    {
        // if wb[i] is false, then check if current prefix can make it true.
        // Current prefix is “str.substr(0, i)”
        if (wb[i] == false && dictionaryContains( str.substr(0, i) )){
            wb[i] = true;
        //cout<<str.substr(0, i)<<wb[i]<<“n”;
        }
        // wb[i] is true, then check for all substrings starting from
        // (i+1)th character and store their results.
        if (wb[i] == true)
        {
            // If we reached the last prefix
            if (i == size)
                return true;

            for (int j = i+1; j <= size; j++)
            {

                if (wb[j] == false && dictionaryContains( str.substr(i, j-i) )){
                    wb[j] = true;
                }
                // If we reached the last character
                if (j == size && wb[j] == true)
                    return true;
            }
        }
    }

    for (int i = 1; i <= size; i++)
        cout<<str.substr(0, i) << “-” <<wb[i]<<“n”;

    // If we have tried all prefixes and none of them worked
    return false;
}

// Driver program to test above functions
int main()
{
    wordBreak(“ilikemngo”)? cout <<“Yesn”: cout << “Non”;
    return 0;
}
OutPut of Above Programm

 
i-1
il-0
ili-0
ilik-0
ilike-1
ilikem-0
ilikemn-0
ilikemng-0
ilikemngo-0

You can see working code and understand more at  : http://ideone.com/rvQZdI

Code courtesy : geeksforgeeks.org

Similar Articles

Filed Under: Amazon Interview Question, Flipkart Interview Questions, Interview Questions, Microsoft Interview Questions, problem Tagged With: Dynamic Programming, string

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

FizzBuzz Solution C C++

Stock Buy Sell to Maximize Profit

Convert Decimal to Roman numbers / Romanizer HackerEarth Code

Add Sub Multiply very large number stored as string

Find min element in Sorted Rotated Array (With Duplicates)

How strtok() Works

SAP Off Campus Hiring_ March 2015 Sample Questions

Best Java Book | Top Java Programming Book for Beginners

Check if an array has duplicate numbers in O(n) time and O(1) space

Adobe Interview Questions 8 month Exp

Find loop in Singly linked list

Print all nodes that are at distance k from a leaf node

TicTacToe Game As Asked in Flipkart

Daughter’s Age VeryGood Puzzle

BlueStone E-commerce Interview Experience

Find two non repeating elements in an array of repeating elements

N teams are participating. each team plays twice with all other teams. Some of them will go to the semi final. Find Minimum and Maximum number of matches that a team has to win to qualify for finals ?

Skiing on Mountains Matrix

VMWare Openings

Singly linked list

Diagonal Traversal of Binary Tree

ADOBE Aptitude C Language Test

Serialise Deserialise N-ary Tree

Binary Tree in Java

Find an index i such that Arr [i] = i in array of n distinct integers sorted in ascending order.

Find Percentage of Words matching in Two Strings

SAP Interview Questions

Implement LRU Cache

Printing Longest Common Subsequence

Count Possible Decodings of a given Digit Sequence

Copyright © 2025 · Genesis Framework · WordPress · Log in