Formatted question description:

140	Word Break II

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"].


If the memory array is not used for optimization to reduce repeated calculations, then the recursive method is no different from brute force, and it will not pass OJ with a high probability. So we have to avoid duplicated counting.

To cache this intermediate result, since we must save s and all of its split strings at the same time, a HashMap can be used to establish the mapping between the two, then in the recursive function, we first detect the current s whether there is a mapping, if so, return directly.

If s is empty, an empty string is returned.



public class Word_Break_II {

    public static void main(String[] args) {
        Word_Break_II out= new Word_Break_II();
        Solution_dfs s = Solution_dfs();

        Set<String> dict = new HashSet<String>();

        List<String> r = s.wordBreak("catsanddog", dict);;

    public class Solution_dfs {

        Map<String, List<String>> hm = new HashMap<>();

        public List<String> wordBreak(String s, Set<String> dict) {

            if (hm.containsKey(s)) return hm.get(s);

            // @note: I failed here by "return new Arraylist()", then "for (String rem: remainderList) {" will not initiate
            if (s.isEmpty()) return Arrays.asList("");

            List<String> list = new ArrayList<String>();
            for (String each: dict) {
                if (each.length() > s.length() || !s.substring(0, each.length()).equals(each)) {

                List<String> remainderList = wordBreak(s.substring(each.length()), dict);

                for (String rem: remainderList) {
                    list.add(each + (rem.isEmpty()? "": " ") + rem);

            hm.put(s, list);

            return list;

    public class Solution {

        List<String> list = new ArrayList<String>();

        public List<String> wordBreak(String s, Set<String> dict) {

            if (s == null || dict == null || dict.size() == 0)  return list;

            // hashmap, from "index of s", to "previous index"
            HashMap<Integer, HashSet<Integer>> hm = new HashMap<Integer, HashSet<Integer>>();

            int length = s.length();
            boolean[] dp = new boolean[length + 1];
            dp[0] = true;

            for (int i = 0; i < length + 1; i++) {

                if (dp[i] == false)  continue;

                for (String each: dict) {

                    if (i + each.length() > length)  continue;

                    if (s.substring(i, i + each.length()).equals(each)) {

                        dp[i + each.length()] = true;

                        // 注意hashmap里放的是index
                        if (hm.containsKey(i + each.length())) {
                            hm.get(i + each.length()).add(i); // start of next word, add current i as previous index
                        } else {
                            HashSet<Integer> st = new HashSet<Integer>();
                            hm.put(i + each.length(), st);

            if (!dp[length])    return list;

            trackback(hm, s, length, "");

            return list;

        // 其实可以直接存,不需要多这一个method
        public void trackback(HashMap<Integer, HashSet<Integer>> hm, String s, int current, String result) {

            if (current == 0) {

                result = result.substring(1);

            for(int prev: hm.get(current)) {

                trackback(hm, s, prev, " " + s.substring(prev, current) + result);


All Problems

All Solutions