[LeetCode] 140. Word Break II

Posted on | In

Problem

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

Note:

  • The same word in the dictionary may be reused multiple times in the segmentation.
  • You may assume the dictionary does not contain duplicate words.

Example 1:

1
2
3
4
5
6
7
8
Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
  "cats and dog",
  "cat sand dog"
]

Example 2:

1
2
3
4
5
6
7
8
9
10
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
3
4
5
Input:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
Output:
[]

Explanation

  1. When the question asks to return all different situation, we can usually use recursion to solve it.

  2. First, we can think of how we solve it in a manual way. From the above example 1, we will find if any string from the wordDict can be the beginning of the s. We can check it using the length of string and if s[0:stringFromArr.length] == stringFromArr, then the stringFromArr can be the beginning of s. In example1, we find out cat and cats both can be the beginning of s. If we choose cat, then s becomes “sanddog”. We again find the beginning string from the wordDict, then we find out “sand” also from the beginning of the string, then s becomes “dog”, and it also inside the wordDict, this mean we find out result string.

  3. This method can use recursion to solve it because when s is changed, the way to solve is the same. This is a brute force way, and we are doing repeated work. For example, when s becomes “sanddog”, we know it can split to “sand” and “dog”. If we face “sanddog” again, then we don’t want to recursive to solve again, we want to save this result. Because we have to save s and the its splitted strings at the same time, then we can use a hashmap<String, List<String>>.

  4. In the recursion function, the base case will be if the map has key, then we just return the value. If s is empty, then we return an empty string inside an array because between each string, there’s a space, but at the end, there’s no space.

  5. In summary, we iterate the wordDict array, and check if a string word can be the beginning of s, then we pass its following string to the recursive function and save the result array as rem. Then, we iterate each result string in rem and concatnate word to form one string, and push this string to the result array.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    HashMap<String, List<String>> map = new HashMap<>();

    public List<String> wordBreak(String s, List<String> wordDict) {
        if (map.containsKey(s)) return map.get(s);
        if (s.equals("")) return Arrays.asList(s);

        List<String> res = new ArrayList<>();
        for (String word : wordDict) {
            int len = word.length();
            if (len > s.length() || !s.substring(0, len).equals(word)) continue;

            List<String> rem = wordBreak(s.substring(len), wordDict);
            for (String str : rem) {
                res.add(word + (str.equals("") ? "" : " ") + str);
            }
        }

        map.put(s, res);
        return res;
    }
}