Problem

Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Examples

Example 1:

1
2

Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]

Example 2:

1
2
3

Input: s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"]
Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

1
2

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: []

Solution

We have already seen part 1 of the problem - Word Break 1 - Check if word is breakable. Instead of using a boolean array to track the matched positions, we need to track the actual matched words.

Method 1 - Backtracking

We have seen Word Break 1 - Check if word is breakable#Method 1 - Brute force - Generate all substrings. We will use solution similar to Subsets.

Video Explanation

Here is the video explanation:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public class Solution {
	public List<String> wordBreak(String s, List<String> wordDict) {
		List<String> ans = new ArrayList<>();
		dfs(s, new HashSet<String>(wordDict), 0, ans, new ArrayList<>());
        return ans;
	}

	private void dfs(String s, Set<String> set, int idx, List<String> ans, List<String> subAns) {
		if (idx == s.length()) {
			if (subAns.size() > 0) {
				ans.add(String.join(" ", subAns));
			}
			return;
		}
        for(int i = idx + 1; i <= s.length(); i++) {
	        String sub = s.substring(idx,i);
            if(set.contains(sub)) {
	            subAns.add(sub);
	            dfs(s, set, i, ans, subAns);
                subAns.remove(subAns.size() - 1);
            }
        }
	}
}

Complexity

  • ⏰ Time complexity: O(2^n)
  • 🧺 Space complexity: O(n + m) - where n is the length of string s, and m is number of words in dict

Method 2 - Dynamic Programming

#TODO use DP solution used in Word Break 1 - Check if word is breakable.

Method 3 - Using Trie

#TODO work on this solution later