Problem

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Examples

Example 1:

1
2
3
4
5

Input:
s = "leetcode", wordDict = ["leet","code"]
Output:
 true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

1
2
3
4
5
6

Input:
s = "applepenapple", wordDict = ["apple","pen"]
Output:
 true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

Example 3:

1
2
3
4

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

Follow up

Word Break 2 - Construct a sentence

Solution

Method 1 - Brute force - Generate all substrings

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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

	private boolean dfs(String s, Set<String> set, int idx) {
		if (idx == s.length()) {
			return true;
		}
        for(int i = idx + 1; i <= s.length(); i++) {
            if(set.contains(s.substring(idx,i)) && dfs(s, set, i)) {
                return true;
            }
        }

		return false;
	}
}

Complexity

  • ⏰ Time complexity: O(2^n)
  • 🧺 Space complexity: O(1)

Method 2 - Looping Over Dict

This is very similar to method 1, but we can also loop on wordDict to do the break. As dictionary size is smaller than string s, we can loop over all the words in dict. For word w in dictionary, we can check if w exists in string and look for remaining string to break.

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

public class Solution {
	public boolean wordBreak(String s, List<String> wordDict) {
		return canBreak(s, new HashSet<>(wordDict), 0);
	}

	public boolean canBreak(String s, Set<String> dict, int idx) {
		if (idx == s.length()) {
			return true;
		}

		for (String word: dict) {
			int len = word.length();
			int end = idx + len;

			//end index should be<= string length
			if (end > s.length()) {
				continue;
			}

			if (s.substring(idx, idx + len).equals(word)) {
				if (canBreak(s, dict, idx + len)) {
					return true;
				}
			}
		}

		return false;
	}
}

Complexity

  • ⏰ Time complexity: O(2^n)
  • 🧺 Space complexity: O(1)

Method 3 - Top Down DP - DFS with memoization

In method 1, if the size of the dictionary is very large, the time is bad. Instead we can solve the problem in O(n^2) time (n is the length of the string).

Repetitive Subproblems

The recursive solution has many subproblems that are repeating at various stage of the recursion. For example, for string abcd the recursion tree will look like

1
2
3
4
5

           abcd
          / \   \     
        bcd  cd  d
       /   \  |
      cd   d  d

We can see that subproblems for “cd” is repeating twice. So, we can cache the solution.

Code

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

public class Solution {
	public boolean wordBreak(String s, List<String> wordDict) {
		return dfs(s, new HashSet<String>(wordDict), 0, new Boolean[s.length()]);
	}

	private boolean dfs(String s, Set<String> set, int idx, Boolean[] cache) {
		if (idx == s.length()) {
			return true;
		}
		if (cache[idx] != null) {
			return cache[idx];
		}
        for(int i = idx + 1; i <= s.length(); i++) {
            if(set.contains(s.substring(idx,i)) && dfs(s, set, i, cache)) {
                return cache[idx] = true;
            }
        }

		return cache[idx] = false;
	}
}

Complexity

  • ⏰ Time complexity: O(n^3 + m). Where n - length of string s and m - number of words in dict. We have n paths in dfs, and then we loop from idx + 1 to n, and then we create substring which takes O(n) time, hence overall O(n^3), plus O(m) time to make set.
  • 🧺 Space complexity: O(n + m) - for recursive state, and m for storing values in set.

Method 4 - Bottom up DP

We can convert previous approach into bottom-up DP. Lets dp[i] represents if substring(0,i) is breakable. Now, for each substring, we will check and fill in the dp[i].

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 boolean wordBreak(String s, List<String> wordDict) {
	    int n = s.length();
        if(n == 0) {
	        return false;
	    }
	    Set<String> set = new HashSet<>(wordDict);
	    
        boolean[] dp = new boolean[n + 1];
        // an empty string can always be formed 
        // without using any word from wordDict
        dp[0] = true; 
        for(int i = 1; i <= n; i++){
            for(int j = 0; j < i; j++){
                if(dp[j] && set.contains(s.substring(j, i))){
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[n];
    }
}

Method 5 - BFS

#TODO - add

Method 6 - Using Trie DS

#TODO - add