Solve the Word Break problem using dynamic programming.?

The Word Break problem can be defined as follows: given a non-empty string ‘s‘ and a dictionary containing a list of non-empty words, determine if ‘s‘ can be segmented into a space-separated sequence of one or more dictionary words.

For example, given the string ‘"leetcode"` and the dictionary ‘["leet", "code"]‘, return true because ‘"leetcode"` can be segmented as ‘"leet code"`.

The dynamic programming approach to this problem involves breaking down the problem into smaller subproblems and solving them incrementally. We can use an array ‘dp‘ of size ‘n+1‘, where ‘n‘ is the length of the input string, to keep track of whether a substring of ‘s‘ from index ‘0‘ to ‘i-1‘ can be segmented into dictionary words. Initially all values in ‘dp‘ are set to false.

We start by setting the first element of ‘dp‘ to true since an empty string can always be segmented. We then iterate over the input string from left to right, and for each index ‘i‘, we check whether there exists a j such that ‘dp[j]‘ is true (meaning that the substring from index 0 to j-1 can be segmented) and the substring from index j to i-1 is a dictionary word. If such index j exists, we set ‘dp[i]‘ to true.

Once we have iterated over the entire input string, the value of ‘dp[n]‘ indicates whether the entire input string can be segmented into dictionary words. If ‘dp[n]‘ is true, then the solution is yes, otherwise it is no.

Here is the Java code implementation of this approach:

public boolean wordBreak(String s, List<String> wordDict) {
    int n = s.length();
    boolean[] dp = new boolean[n+1];
    dp[0] = true;
    
    for(int i=1; i<=n; i++){
        for(int j=0; j<i; j++){
            if(dp[j] && wordDict.contains(s.substring(j,i))){
                dp[i] = true;
                break;
            }
        }
    }
    
    return dp[n];
}

In this implementation, we iterate over all substrings ‘s.substring(j,i)‘ of the input string ‘s‘. If the substring is found in the dictionary and there exists a previous index ‘j‘ such that the substring from index ‘0‘ to ‘j-1‘ can be segmented, we set ‘dp[i]‘ to ‘true‘. By breaking out of the inner loop we avoid unnecessary iterations, as soon as we find that ‘dp[i]‘ is true, we can break the j loop as there is no need to test other ‘j‘ values.

Overall, the time complexity of this algorithm is O(n²), where n is the length of the input string, due to the nested loop over all substrings of ‘s‘. The space complexity is also O(n), as we use an array of size ‘n+1‘ to store the intermediate results of the dynamic programming algorithm.