140. Word Break II

Problem Statement

Word Break II - LeetCode

Pattern: Related: 139. Word Break

---

Solution

HashSet<String> dict;
ArrayList<String> res;
 
public void dp (String S, int start, StringBuilder sb) {
	if(start >= S.length()) {
		sb.setLength(Math.max(sb.length() - 1, 0));
		res.add(sb.toString());
		return;
	}
 
	for (int end = start ; end < S.length() ; end++) {
		String str = S.substring(start, end+1);
		if(dict.contains(str)) {
			dp(S, end + 1, new StringBuilder(sb).append(str).append(" "));
		}
	}
}
 
public List<String> wordBreak(String s, List<String> list) {
	dict = new HashSet<>();
	dict.addAll(list);
	res = new ArrayList<>();
 
	dp(s, 0, new StringBuilder());
	return res;
}

TC : $n^2$ SC :

Notes