140. Word Break II (Hard)

https://leetcode.com/problems/word-break-ii/

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:

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

Example 2:

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:

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

Solutions

class Solution {

    // FIXME Be careful that this problem can never return null, if there is no possible combinations, return empty List.

    // keep track of the substrings that are unable to partition
    Set<String> unpartitionable = new HashSet<>();

    // keep track of the possible partition schemes for specific substring
    Map<String, List<String>> schemes = new HashMap<>();

    public List<String> wordBreak(String s, List<String> wordDict) {
        // See if s or wordDict is null
        if (s == null || s.length() == 0 || wordDict == null || wordDict.isEmpty()) {
            return new ArrayList<>();
        }

        // transfer words from List to Set
        Set<String> dict = new HashSet<>(wordDict);

        // recursively break up the strings, return the possible combinations
        List<String> ans = recurse(s, dict);
        if (ans == null) {
            return new ArrayList<>();
        }

        return ans;
    }

    private List<String> recurse(String str, Set<String> dict) {
        List<String> ans = new ArrayList<>();

        // return empty List if reach the end
        if (str == null || str.isEmpty()) {
            return ans;
        }

        // return null if str is unpartitionable.
        if (unpartitionable.contains(str)) {
            return null;
        }

        // return all the previously partitioned strings if exists
        if (schemes.containsKey(str)) {
            return schemes.get(str);
        }

        // keep the count of the possible partition schemes
        int count = 0;

        // try all the possible splitting schemes, i is the length of current substring.
        for (int i = 1; i <= str.length(); i++) {
            String sub = str.substring(0, i);
            if (!dict.contains(sub)) {
                continue;
            }

            List<String> results = recurse(str.substring(i), dict);

            // str.substring(i) can not be partitioned.
            if (results == null) {
                continue;
            }

            // create new copy of the ans, in case it tampers the results of substrings of str
            results = union(sub, results);

            ans.addAll(results);

            count++;
        }

        // if no partition scheme available, keep this substring to black list
        if (count == 0) {
            unpartitionable.add(str);

            // must return null, otherwise previous level will take it partitionable.
            return null;
        }

        schemes.put(str, ans);

        return ans;
    }

    private List<String> union(String str, List<String> strs) {
        // create a branch new List to hold unioned results
        List<String> ans = new ArrayList<>();
        if (strs.size() == 0) {
            ans.add(str);

            return ans;
        }

        for (String s : strs) {
            ans.add(str + " " + s);
        }

        return ans;
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2020-03-04 01:54:54

results matching ""

    No results matching ""