private ArrayList<String> _wordBreak(String s, Set<String> dict, Map<String, ArrayList<String>> map) {
        if (map.containsKey(s)) {
            return map.get(s);
        }
        ArrayList<String> result = new ArrayList<String>();
        int length = s.length();
        for (int i = 0; i < length; i++) {
            String prefix = s.substring(0, i + 1);
            if(dict.contains(prefix)) {
                ArrayList<String> tail = _wordBreak(s.substring(i+1, length), dict, map);
                for (String str : tail) {
                    result.add(prefix + str + " ");
                }
            }
        }
        map.put(s, result);
        return result;
    }