public ArrayList<String> wordBreakII(String s, Set<String> dict) {
        ArrayList<String> result = new ArrayList<String>();
        if(s.equals("") || !wordBreak(s, dict))
            return result;

        int length = s.length();
        boolean [] dp = new boolean[length + 1];
        HashMap<Integer, ArrayList<String>> segmentedString = new HashMap<Integer, ArrayList<String>>();
        Arrays.fill(dp, false);
        dp[0] = true;
        for(int i = 0; i <= length; i++){
            segmentedString.put(i, new ArrayList<String>());
            segmentedString.get(i).add("");
        }

        for(int i = 1; i <= length; i++){
            for(int j = 0; j < i; j++){
                if(dp[j] && dict.contains(s.substring(j, i))){
                    dp[i] = true;
                    segmentedString.get(i).remove("");
                    for(String item: segmentedString.get(j)){
                        if(item.equals(""))
                            segmentedString.get(i).add(s.substring(j, i));
                        else
                            segmentedString.get(i).add(item + " " + s.substring(j, i));
                    }
                }
            }
        }
        return segmentedString.get(length);
    }