Coderust: Hacking the Coding Interview/

...

/

Word Break Problem

Word Break Problem

Given a dictionary of words and an input string, tell whether the input string can be segmented into dictionary words.

We'll cover the following...

Statement

We’re given a dictionary of words and an input string. Find out whether the input string can be completely segmented into the words of a given dictionary. Input string and the dictionary words will not contain spaces.

Examples

The following two examples elaborate this problem further:

Sample input

Return true if the input string can be segmented. Otherwise false if it can not be segmented.

Words dictionary: ["apple", "pear", "pier", "pie"]
Input string: "applepie"

Expected output

True

Try it yourself

#include <string>
#include <unordered_set>
#include <iostream>
using namespace std;
bool CanSegmentString(string inputString, unordered_set<string> &dictionary) {
	//TODO: Write - Your - Code
	return false;
}

Solution

We can solve this problem by segmenting the large string at each possible position to see if the string can be completely segmented into words in the dictionary. If we write the algorithm in steps, it will be as follows:

n = length of input string
for i = 0 to n - 1
  first_word = substring (input string from index [0, i] )
  second_word = substring (input string from index [i + 1, n - 1] )
  if dictionary has first_word
    if second_word is in dictionary OR second_word is of zero length, then return true
    recursively call this method with second_word as input and return true if it can be
    segmented

The algorithm computes two strings from scratch in each iteration of the loop. In the worst case, in each iteration of the loop, there would be a recursive call to check the segmentation of second_word in each iteration of the loop. This shoots the time complexity up to 2n2^n.

Let’s try this method on the following example:

#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>
using namespace std;
bool CanSegmentString(string input_string, unordered_set<string>& dictionary) {
	for (int i = 1; i <= input_string.length(); ++i) {
		string first = input_string.substr(0, i);
		// Check if the first part exists in the dictionary
		if (dictionary.find(first) != dictionary.end()) {
			string second = input_string.substr(i);
			if (second.empty()) {
				return true;
			}
			// Check if the second part exists in the dictionary
			if (dictionary.find(second) != dictionary.end()) {
				return true;
			}
			// Recursive call
			if (CanSegmentString(second, dictionary)) {
				return true;
			}
		}
	}
	return false;
}
int main() {
	string s = "hellonow";
	vector<string> input_str = {"hellonow", "nowok", "applepie",
									   "applejuice"};
	vector<vector<string> > words_dict = {{"hello", "hell", "on", "now"},
										  {"hello", "hell", "on", "now"},
										  {"apple", "pear", "pier", "pie"},
										  {"apple", "pear", "pier", "pie"}};
	for (int i = 0; i < input_str.size(); i++) {
		unordered_set<string> dict(words_dict[i].begin(), words_dict[i].end());
		cout << i + 1 << ". Words dictionary: ";
		PrintList(words_dict[i]);
		cout << "   Input string: " << input_str[i] << endl;
		if (CanSegmentString(input_str[i], dict)) {
			cout << "   Result: String can be segmented" << endl;
		} else {
			cout << "   Result: String can not be segmented" << endl;
		}
		cout << "---------------------------------------------------------------------------------------------------\n" << endl;
	}
}

We can see that we may be ...

Access this course and 1400+ top-rated courses and projects.