private List<String> solution2(String s, Set<String> dict) {
        Map<Integer, List<String>> result = new HashMap<Integer, List<String>>();
        ArrayList<String> l = new ArrayList<String>();
        l.add("");
        result.put(0, l);

        for (int i = 1; i <= s.length(); i++) {
            ArrayList<String> list = new ArrayList<String>();
            for (String word : dict) {
                if (word.length() > i) {
                    continue;
                } else {
                    if (word.equals(s.substring(i - word.length(), i))) {
                        if (!result.get(i - word.length()).isEmpty()) {
                            for (String item : result.get(i - word.length())) {
                                list.add((item + " " + word).trim());
                            }
                        }
                    }
                }
            }
            result.put(i, list);
        }

        return result.get(s.length());
    }