Word Break Editorial

Practice Problem Link: https://workat.tech/problem-solving/practice/word-break

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. You have to determine if s can be broken down into a sequence of words where each word is an element in w.

Naive Approach

We can try to check every prefix of the string, and check if it is in the given list. If it is found, we recursively solve for the rest of the string in the same way, using backtracking. If none of the substrings match, then the result is false.

Analysis

• Time Complexity: Exponential
• Space Complexity: O(1)

Implementation

C++

bool wordBreakUtil(string s, int start, vector<string> &w) {
	if (start == s.size()) {
		return true;
	}
	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(wordBreakUtil(s, i + 1, w)) {
					return true;
				}
			}
		}
	}
	return false;
}
bool wordBreak (string s, vector<string> &w) {
    return wordBreakUtil(s, 0, w);
}

Java

class Solution {
	boolean wordBreakUtil(String s, int start, String[] w) {
		if (start == s.length()) {
			return true;
		}
		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(wordBreakUtil(s, i + 1, w)) {
						return true;
					}
				}
			}
		}
		return false;
	}
	boolean wordBreak (String s, String[] w) {
	    return wordBreakUtil(s, 0, w);
	}
}

Optimal Approach

We can observe that the above naive approach has several overlapping subproblems, which get repeated again and again in the function calls. So, we can Dynamic Programming to solve the above problem, by memoizing the repetitive function calls.

Analysis

• Time Complexity: O(n * |s|)
• Space Complexity: O(|s|)

Implementation (Iterative)

C++

bool wordBreak (string s, vector<string> &w) {
    unordered_set<string> storeWords;
	for (string st: w) {
		storeWords.insert(st);
	}
	int n = s.length();
	vector<bool> dp(n + 1);
	dp[0] = 1;
	for (int i = 0; i <= n; i++) {
		for (int j = i; j >= 0; j--) {
			if(dp[j] == 1 && (i - j) <= n && storeWords.find(s.substr(j, i - j)) != storeWords.end()) {
				dp[i] = 1;
			}
		}
	}
	return dp[n];
}

Java

class Solution {
	boolean wordBreak (String s, String[] w) {
	    Set<String> storeWords = new HashSet<String>();
		for(int i = 0; i < w.length; i++) {
			storeWords.add(w[i]);
		}
		int n = s.length();
		boolean[] dp = new boolean[n + 1];
		dp[0] = true;
		for (int i = 1; i <= n; i++) {
			for (int j = i; j >= 0; j--) {
				if(dp[j] == true && (i - j) <= n && storeWords.contains(s.substring(j, i))) {
					dp[i] = true;
				}
			}
		}
		return dp[n];
	}
}

Implementation(Recursive)

C++

vector<int> dp;
bool wordBreakUtil(string s, int start, vector<string> &w) {
	if (start == s.size()) {
		return true;
	}
	if(dp[start] != -1) {
		return dp[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(wordBreakUtil(s, i + 1, w)) {
					return dp[start] = true;
				}
			}
		}
	}
	return dp[start] = false;
}
bool wordBreak (string s, vector<string> &w) {
	dp.assign(s.length() + 1, -1);
    return wordBreakUtil(s, 0, w);
}

Java

class Solution {
	Boolean dp[];
	boolean wordBreakUtil(String s, int start, String[] w) {
		if (start == s.length()) {
			return true;
		}
		if(dp[start] != null) {
			return dp[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(wordBreakUtil(s, i + 1, w)) {
						return dp[start] = true;
					}
				}
			}
		}
		return dp[start] = false;
	}
	boolean wordBreak (String s, String[] w) {
		dp = new Boolean[s.length() + 1];
	    return wordBreakUtil(s, 0, w);
	}
}