Question

link

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

Stats

Adjusted Difficulty 5
Time to use --------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is a tough question. Standard DFS search would work, but we need to check ‘breakable’ first. Otherwise, I got TLE.

Check breakable is a easy DP, and we do not need to remove any elements from the dictionary. (Word ladder needs remove elements from dictionary, don’t confuse them).

Solution

Updated on July 4th, 2014. The DFS code actually standard, but keep in mind to check breakable first (using DP).

Code

DFS with pruning and DP breakable check, with the again-updated code on Sep 12th, 2014.

public List<String> wordBreak(String s, Set<String> dict) {
    List<String> ans = new ArrayList<String>();
    if (s == null || s.length() == 0 || dict == null) {
        return ans;
    } else if (!canBreak(s, dict)) {
        return ans;
    }
    helper(ans, "", s, 0, dict);
    return ans;
}

private void helper(List<String> ans, String str, String s, int pos, Set<String> dict) {
    int len = s.length();
    if (pos == len) {
        ans.add(str.substring(1));
        return;
    }
    for (int i = pos; i < len; i++) {
        String sub = s.substring(pos, i + 1);
        if (dict.contains(sub)) {
            helper(ans, str + " " + sub, s, i + 1, dict);
        }
    }
}

public boolean canBreak(String s, Set<String> dict) {
    if (s == null || s.length() == 0) {
        return true;
    }
    int len = s.length();
    boolean[] dp = new boolean[len + 1];
    dp[0] = true;
    for (int i = 1; i <= len; i++) {
        for (int j = 0; j < i; j++) {
            if (!dp[j]) {
                continue;
            }
            if (dict.contains(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[len];
}

Updated Oct 29, 2022


public List<String> wordBreak(String s, List<String> wordDict) {
    Set<String> dict = new HashSet<String>();
    for (String str: wordDict) {
        dict.add(str);
    }

    List<String> ans = new ArrayList<String>();
    helper(ans, "", s, 0, dict);
    return ans;
}

private void helper(List<String> ans, String str, String s, int pos, Set<String> dict) {
    int len = s.length();
    if (pos == len) {
        ans.add(str.substring(1));
        return;
    }
    for (int i = pos; i < len; i++) {
        String sub = s.substring(pos, i + 1);
        if (dict.contains(sub)) {
            helper(ans, str + " " + sub, s, i + 1, dict);
        }
    }
}