Datastructures & Algorithms in Java – Dynamic Programming – Word Break

Problem:

Given a word , find if the word could be formed by joining words together from a given dictionary.

Example:

The word “datastructure” can be formed using the words from the dictionary:

[“data”,”algorithms”,”structure”]

So ,the output is true.

For the word “breadandbiscuit”

and the dictionary [“and”,”bis”,”bread”]

the output is false

Assumptions:

• The words and the dictionary words are all in small case
• The input word can contain duplicate sub strings
• The dictionary contains unique words

Try out the solution here:

https://leetcode.com/problems/word-break/

Solution:

Hint:

• Use dynamic programming , for each substring in the given word find if the substring exists in the dictionary , use this information to check if the remaining substring can be formed using the words in the dictionary.

You can find a solution using recursion as well but the time complexity is huge.

Here is the code:

Recursion Code:

The basic idea is for every substring in the given word , check if it is present in the dictionary.

If it is present , find if the remaining substring is present in the dictionary in a recursive way (since the remaining substring can be further split into several substrings and each in turn need to be checked if present in the dictionary in a recursive way)

   
class Solution {
public boolean wordBreak(String s, List wordDict) {

 return wordBreakRecursion(s,wordDict,0);
}



public boolean wordBreakRecursion(String word,List<String> dictionary,int startOfWord){


    if(word.length() == startOfWord){

        return true;
    }


    for(int i=startOfWord+1;i<=word.length();i++){


        if(dictionary.contains(word.substring(startOfWord,i)) && wordBreakRecursion(word,dictionary,i)){

            return true;
        }
    }

    return false;
}

}

There is a recursion call made for every letter in the input and these recursion calls in turn make multiple recursion calls again based on the remaining substring length.

A better solution exists using Dynamic programming:

In dynamic programming you store the result of whether a substring is present in the dictionary or not in an array and use this information to further find out if the remaining substring is present in the dictionary or not.

You cut out the recursive calls this way.

ALGORITHM:

STEP1: Initialize an array , which is one length greater than the length of the word

STEP2: Initialize the first value at index 0 to be true , since this represents a blank word and it is assumed to be present in the dictionary

STEP3: For each letter in the word and for each letter “l” before the current letter, check if the substrings present before the letter “l” are present in the dictionary by checking the output array and check if the substring present after the letter “l” (including it) is present in the dictionary by checking it directly.

STEP3b: If the they are both present , mark the current value in the output array to be true (meaning until the current index , the given substring can be formed using the words in the dictionary – all you have to do now is see if the remaining substring can be formed as well)

STEP4: Return the last value in the output array which indicates if the entire word can be formed by using words from the dictionary.

Dynamic Programming Code:

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

Time complexity of the above algorithm is time taken for the first for loop multiplied by time taken by the second for loop multiplied by time taken for the “substring” method which is O(n³)

That’s it!