Word Break - II Editorial

Practice Problem Link: Word Break II

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

You are given a string s and a word list w which is a list of unique strings. Break the string into a sequence of words where each word is an element in w.

Naive Approach

Traverse the given string and check for every substring. If a substring is present in the list then recursively check the remaining string until the end of the string is reached. Store all the valid combinations.

Analysis

• Time Complexity: Exponential
• Auxiliary Space Complexity: O(Size of s)

Implementation

C++

void getSentences(string s, int start, string word, vector<string> &w, vector<string> &allSentences) {
	if (start == s.size()) {
		allSentences.push_back(word);
		return;
	}
	for (int i = start; i < s.size(); i++) {
		string currWord = s.substr(start, i - start + 1);
		for(int j = 0; j < w.size(); j++) {
			if (currWord == w[j]) {
				currWord = word + currWord;
				if (i != s.size() - 1) {
					currWord += " ";
				}
				getSentences(s, i + 1, currWord, w, allSentences);
			}
		}
	}
}
vector<string> wordBreak (string s, vector<string> &w) {
    vector<string> allSentences;
	string word;
	getSentences(s, 0, word, w, allSentences);
    return allSentences;
}

Java

class Solution {
	static List<String> allSentences;
	void getSentences(String s, int start, String word, String[] w) {
		if (start == s.length()) {
			allSentences.add(word);
			return;
		}
		for (int i = start; i < s.length(); i++) {
			String currWord = s.substring(start, i + 1);
			for(int j = 0; j < w.length; j++) {
				if (currWord.equals(w[j])) {
					currWord = word + currWord;
					if (i != s.length() - 1) {
						currWord += " ";
					}
					getSentences(s, i + 1, currWord, w);
				}
			}
		}
	}
	List<String> wordBreak (String s, String[] w) {
	    allSentences = new ArrayList<String> ();
		String word = "";
		getSentences(s, 0, word, w);
		return allSentences;
	}
}

Optimal Approach

The idea is similar to the naive solution but to avoid computation for each substring multiple times, we can memoize the subproblems so that the result of overlapping intervals can be computed in constant time.

Analysis

• Time Complexity: O(n2 * w)
• Auxiliary Space Complexity: O(n2)

Where n is the size of string s and w is the size of the list w.

Implementation

C++

unordered_map<int, vector<string>> memoize;
vector<string> getSentences(string s, int start, vector<string> &w) {
	vector<string> subSequence, nextSequence;
	if (memoize.find(start) != memoize.end()) {
		return memoize[start];
	}
	for (int i = start; i < s.size(); i++) {
		string currWord = s.substr(start, i - start + 1);
		for(int j = 0; j < w.size(); j++) {
			if (currWord == w[j]) {
				if (i + 1 == s.size()) {
					subSequence.push_back(currWord);
				} else {
					nextSequence = getSentences(s, i + 1, w);
			 		for (int k = 0; k < nextSequence.size(); k++) {
						subSequence.push_back(currWord + " " + nextSequence[k]);
					}
				}
				break;
			}
		}
	}
	memoize[start] = subSequence;
	return subSequence;
}
vector<string> wordBreak (string s, vector<string> &w) {
	memoize.clear();
	return getSentences(s, 0, w);
}

Java

class Solution {
	HashMap<Integer, List<String>> memoize = new HashMap<Integer, List<String>>();
	List<String> getSentences(String s, int start, String[] w) {
		List<String> subSequence = new ArrayList<String>();
		List<String> nextSequence = new ArrayList<String>();
		if (memoize.containsKey(start)) {
			return memoize.get(start);
		}
		for (int i = start; i < s.length(); i++) {
			String currWord = s.substring(start, i + 1);
			for(int j = 0; j < w.length; j++) {
				if (currWord.equals(w[j])) {
					if (i + 1 == s.length()) {
						subSequence.add(currWord);
					} else {
						nextSequence = getSentences(s, i + 1, w);
						for (int k = 0; k < nextSequence.size(); k++) {
							subSequence.add(currWord + " " + nextSequence.get(k));
						}
					}
					break;
				}
			}
		}
		memoize.put(start, subSequence);
		return subSequence;
	}
	List<String> wordBreak (String s, String[] w) {
	    memoize.clear();
		return getSentences(s, 0, w);
	}
}