# 130.Word Break II

Question link is here.

And by the way, I want to improve my Java fluency now, so from today on, the solution will be in Java.

# Description

Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]

Example 2:

Input: s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"]
Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: []

# Solution

# Dynamic Programming + Hash + Recursion

# Hash

First, in order to quickly check if one substring of s is in the wordDict, we need to use wordDict to build a hashset.

# Recursion

Second, we need to divide string s into serval parts, and each part needs to be in the hashset. So, the idea is that once we find a word, we need to check if the remaining substring can be divided in to serval words.

So, for example.

word = "catsanddog".

wordDict = ["cat","cats","and","sand","dog"].

First, we find that "cat" is in the dict, than we need to check if "sanddog" can be divided. So we pass "sanddog" to the next level of recursion.

# Dynamic Programming

The purpose of Dynamic Programming is that we store some useful information, so, we don't need to calculate it again. This helps the algorithm has a low Time Complexity.

In this case, we frequently needs to check if a substring of s is in the dict. Than, we can use dp to store that.

// note here s.substring(i,j) means the substring starts at i, ends at j. 
// Both i and j are included.

int[][] dp = int[s.length][s.length];
dp[i][j] = 1, if s.substring(i,j) is in the worddict
dp[i][j] = 0, otherwise

After we computed dp, we can take advanged of the dp array we constructed.

We start with the first row of dp, whenever we find dp[0][i] == 1, we start the recursion at the i+1 line, and check if there exists any j, that $dp[i+1][j] == 1$ . Than we would have there possible result.

If there isn't any j that $dp[i+1][j] == 1$ , the current path is not working, so we need to delete it. In my code, it use "-" to denote this situation.
If $dp[i+1][j] == 1$ and $j==s.length-1$ , than we end this recursion and we return the s.substring[i+1,j] for previous recursion to form the sentences.
And $dp[i+1][j] == 1$ and $j < s.length-1$ , we start the next level of recursion.

And for each level of recursion, we need to use the currentWord and the result that next level of recursion returned to form the sentences, and return them to the previous level of recursion.

So solution is like this:

class Solution {
    public ArrayList<String> res = new ArrayList<>();
    public HashSet<String> dict = new HashSet<>();
    public int[][] dp = null;
    public int length = 0;
    public String totalString = null;

    public ArrayList<String> helper(int start) {
        ArrayList<String> returnString = new ArrayList<>();
        
        //iterate through i to end, check every possible word exists
        for(int i = start; i < length; i++) {

            //we have found a word
            if(dp[start][i] == 1){
                String currentWord = totalString.substring(start, i+1); //get the current word

                //we have reach to the end, so only the currentWord needs to be returned.
                if(i+1>=length){
                    returnString.add(currentWord);
                    return returnString;
                }

                // otherwise, we start recursion from index i+1
                ArrayList<String> followedWords = helper(i+1);

                //iterate through all valid sentences that s.substring(i+1, length+1) can form.
                //and we add currentWord to the head of each sentences
                //than we return it.
                for(String eachString:followedWords) {
                    //if some sentence equals "-", than the sentence is not valid, so we don't use it.
                    if(!eachString.equals("-")) {
                        returnString.add(currentWord + " " + eachString);
                    }
                }
            }
        }

        //if there isn't any valid solution, we return "-";
        if(returnString.size() == 0) {
            returnString.add("-");
        }
        return returnString;
    }

    public List<String> wordBreak(String s, List<String> wordDict) {
        totalString = s;
        length = s.length();
        for(String temp: wordDict)
            dict.add(temp);
        dp = new int[length][length];

        //build dp
        for(int i = 0; i < length; i++){
            for(int j = i+1; j <= length; j++) {
                String sub = s.substring(i, j);
                if(dict.contains(sub)){
                    dp[i][j-1] = 1;
                }
            }
        }
        //start recursion at index 0
        res = helper(0);

        //corner case that nothing can be formed
        //return empty ArrayList;
        if(res.size()==1 && res.get(0).equals("-")) {
            return new ArrayList<String>();
        }
        return res;
    }
}

Time Complexity $O(N^2 + 2^N + W)$

N: length of String
W: number of words
$N^2$ : time to build dp array
$2^N$ : worst case that we have $2^N$ sentences. I.E. a break inserted in the every adjacent chars.
W: time to build the hashset

Leetcode 130