Word Break Coding Question-Asked in Google Interviews.

Problem Statement :

Given a string A and a dictionary of n words B, find out if A can be segmented into a space-separated sequence of dictionary words.

Input Format:

The first line of the input contains an integer ’N’, denoting the total number of elements of the dictionary.

It is followed by N strings.

After this, string ‘S’ is entered.

Output Format:

The output contains one line. Output 1 if string S can be made from the N strings of the dictionary. Else output 0.

Given:

12
i 
like
sam
sung
samsung
mobile
icecream
man
go
mango
ilike

Output:

1

Explanation of given Test Cases :

The string can be segmented as "i like".

Approach:

The idea is simple, we consider each prefix and search it in the dictionary. If the prefix is present in the dictionary, we recur for the rest of the string (or suffix). If the recursive call for suffix returns true, we return true, otherwise, we try the next prefix. If we have tried all prefixes and none of them resulted in a solution, we return false.

Code:

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.