Word Break

Word Break is a problem that beautifully illustrates a whole new concept. We have all heard of compound words. Words made up of more than two words. Today we have a list of words and all we’ve got to do is check if all the words from the dictionary can fit up to make our compound word. Without wasting any more time let me get to a test case to clear things up a bit.

Example

Input     :      String=LeetCode ; Dictionary:[“Leet”,”Code”]

Output:    true

Let us look into a test case where we should get false as well

Input     :     String=Applepinkraft ; Dictionary:[“Apple”,”Pink”,”Kraft”]

Output:     false

Explanation

Let us look into the first test case for solving this word-break problem.

• We create a boolean array for all the characters. Let it be check.
• We will set the  default values to false
• check[i]=true if substring(0, i) can be assembled from the words in the dictionary
• check[0]=true as substring(0,0) satisfies the condition
• For each i
  • We loop over all possible substrings.
  • What makes a substring eligible?
    • It should start from the end of the last segment i.e check[j]=true
    • substring(j, i) shall be a part of the dictionary
  • Mark check[i] true for all eligible substrings
• If check[string.length()] is true we can be assured that the string eligible

The initial boolean array can be pictured as

Array remains the same when the values of I are,2 and 3.

As i=4 we start scanning from 0 and voila!. We have found our first word.

We mark check[4] as true and proceed on with our search

The words that begin from 0 and 4 are both taken into consideration while checking

Just as we find CODE. We turn check[8] to true and thus return true as our answer.

Here is an easy peasy code to go with the above explanation

Implementation

Java Code For Word Break

class Solution 
{
    public boolean wordBreak(String s, List<String> wordDict) 
    {
        boolean check[]=new boolean[s.length()+1];
        check[0]=true;
        for(int i=1;i<=s.length();i++)
        {
            for(int j=0;j<i;j++)
            {
                //check[j] helps us to figure out new words without overlaps
                if(check[j] && wordDict.contains(s.substring(j,i)))
                {check[i]=true;break;}
            }
        }
        return check[s.length()];
    }
}

C++ Code For Word Break

class Solution 
{
public:
    bool wordBreak(string s, vector<string>& vec) 
    {
        vector<bool> check(s.size()+1,false);
        check[0]=true;
        int start=0;
        std::vector<string>::iterator it; 
        for(int i=1;i<=s.length();i++)
        {
            for(int j=start;j<i;j++)
            {
                if(check[j]==true)
                {
                    string word=s.substr(j,i);
                    it = std::find (vec.begin(), vec.end(), word); 
                    if (it != vec.end()) 
                    {check[i]=true;break;}
                }
            }
        }
        return check[s.length()];   
    }
};

String: LeetCode  
Dictionary: ["Leet","Code"]

true

Complexity Analysis

Time complexity: O(n^2) where n is the length of the array. Here we use nested for loop in which the second loop run i times and first-run n times.

Space complexity: O(n) because we create a vector of size n to store the information in terms of true or false.

There are a lot of string problems we have which you can check out for more practice.

References