Concatenated Words Leetcode Solution

Hello and welcome back to the Leetcode Daily series! We have another frustrating problem to deal with today, but that's just what life is, one frustrating problem after another, isn't it?

Let's bash our heads in, um, I mean, solve this problem!

Understanding the Problem

Here's the problem statement for today.

Given an array of strings words (without duplicates), return all the concatenated words in the given list of words.

A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.

Go over these examples to gain a better feel of what the problem is asking us to do.

Example 1:

Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]
Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats"; 
"dogcatsdog" can be concatenated by "dog", "cats" and "dog"; 
"ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".

Example 2:

Input: words = ["cat","dog","catdog"]
Output: ["catdog"]

If you stay consistent enough in your Leetcode journey, sooner or later you'll come across a problem that will make you go, "Huh, this looks like the problem I solved a few days ago...". This is one such problem for me. I'll be explaining both this problem and the problem from where its solution is derived from.

The problem that this is a variation of, is called Word Break. Let's see what this problem asks us to do.

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

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

Example 1:
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".
Example 2:
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

I hope you can see a few subtle similarities between these two problems. Both of them require us to evaluate whether a certain word can be formed by combining any number of words from a given dictionary. The only difference is that today's problem, Concatenated Words, asks us to do this for multiple words, and return those words as the answer.

Let's see how we can solve these problems.

Intuition

Let's see how we can solve the Word Break problem first. The naive solution would be to check every prefix of the target string in the given list of strings. If this prefix is found in the dictionary, we make a recursive call to this function for the remaining portion of the target string. If we find that we've reached the end of the string during some recursive call, we can conclude that the target string can be formed using different words from the given dictionary.

This can be considered a brute-force approach to this problem. It's not an efficient approach at all, but it is where one should start when trying to solve a dynamic programming problem. Try to write up the code for this recursive method before moving forward. If you have any problems, refer to the next section.

The problem with this approach is that there are a lot of repeated calculations. If you try doing a dry run for this algorithm, you'll realize that the recursive function will be called for the same prefix multiple times, because of which your time complexity will shoot up to O(2^n) .

The efficient approach would be to use recursion with memoization. Memoization is a technique used to improve the performance of recursive functions by caching/storing the intermediate results. The idea is to save the result of a function call in memory so that if the same input parameters are passed again, the cached result can be returned instead of re-computing the function.

Try to write up the code using memoization before moving forward. If you have any problems, refer to the next section.

A recursion with memoization solution is good enough for the Word Break problem. Now, let's see how we can use this problem to solve the Concatenated Words problem.

The difference between these two problems is that in the latter one, we don't have a target string. Instead, we need to check whether all the words given in the input can be constructed after concatenating two or more of the other words given in the input or not. So, we just have to perform all the operations we did in the Word Break problem, but for every word in the input. Seems simple enough, doesn't it?

Let's take a look at the algorithm we'll be using for this problem.

Initialize a map, unordered_map<string, int> mp that stores the input words and an array of strings vector<string> ans that will store our answer.

Insert each word given in words into mp .

Initialize an array dp of size 1e5 (the max sum of the lengths of the input strings) with -1. We'll be using this array for storing the intermediate results of our recursive function (memoization).

Iterate through the words array, and for each string, call the recursive helper(string s, int index) function. Before calling this function, we remove the array from mp .

Inside the helper function, do the following:

If the current index is greater than the length of the string s , it means we've reached the end of the string and that the string can be formed by concatenating two or more of some other words in the input array. So, return true. This will be the base condition for our recursive function.

If dp[index] != -1 , it means we've already evaluated the value of the helper function for the given string at the given index. So, instead of performing the same calculation again, we just return the value stored at dp[index].

Iterate through the string from the index i=1 to i<=s.size() . For each index, check if the substring s.substr(index,i) is present in the mp, and make a recursive call to helper(s,index+i) . If the recursive call returns true and the substring is present in mp , assign true to dp[index] and return the same.

Outside the loop, return false, since we'll only reach here if the current string can't be formed using any of the given words in the input.

If helper returns true, insert the current string in ans . Reset dp to -1 and insert the current string back into the map.

Return ans.

Try to think why we removed the current string from the map before calling the helper function and re-inserted it once we returned from the function. If you can't figure it out, remove those two lines of code and see what happens.

Please try to write the code for this solution before moving on to the next section.

Coding Up The Solution

I'll provide codes for all the methods described above for both problems.

Recursive approach for the Word Break problem.

 class Solution {
 public:
     bool wordBreak(string s, vector<string>& wordDict) {
         set<string> word_set(wordDict.begin(), wordDict.end());
         return helper(s, word_set, 0);
     }

     bool helper(string& s, set<string>& word_set, int start) {
         if (start == s.length()) {
             return true;
         }
         for (int end = start + 1; end <= s.length(); end++) {
             if (word_set.find(s.substr(start, end - start)) != word_set.end() and
                 helper(s, word_set, end)) {
                 return true;
             }
         }
         return false;
     }
 };

Note: This approach will return TLE since it has a time complexity of O(2^n).

Recursion with memoization for the Word Break problem.

 class Solution {
 public:
     unordered_map <string, int> mp;
     int dp[10000];
     bool helper(string s, int index){

         if(index >= s.size())
         {
             return true;
         }
         else if(dp[index] != -1)
             return dp[index];
         for(int i = 1 ; i <= s.size() ; i++) {

             if(mp[s.substr(index, i)] && helper(s, index + i)) {
                 return dp[index] =true;
             }
         }

         return dp[index] =  false;
     }
     bool wordBreak(string s, vector<string>& wordDict) {
         memset(dp, -1, sizeof(dp));
         for(auto x: wordDict)
             mp[x] = 1;

         return helper(s,0);
     }
 };

Recursion with memoization for Concatenated Words problem.

 class Solution {
 public:
     unordered_map<string,int> mp;
     int dp[100000];
     bool helper(string s,int index){

         if(index >= s.size()) return true;

         if(dp[index] != -1) return dp[index];

         for(int i = 1; i <= s.size(); i++){
             if(mp[s.substr(index,i)] && helper(s,index+i)){
                 return dp[index] = true;
             }
         }

         return dp[index] = false;

     }
     vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
         vector<string> ans;

         for(string i : words){
             mp[i]++;
         }
         memset(dp,-1,sizeof(dp));

         for(string i : words){
             mp.erase(i);
             if(helper(i,0))
                 ans.push_back(i);
             memset(dp,-1,sizeof(dp));
             mp[i]++;
         }

         return ans;
     }
 };

That's all for today! We covered two very interesting problems today and if you were able to keep up and see the patterns in these problems, kudos to you! If not, don't worry, be consistent and one day you'll be solving these problems without breaking a sweat.

Please leave any suggestions you might have in the comments, and subscribe to my newsletter to stay on top of all the articles I post.

Cheers!

Concatenated Words Leetcode Solution

Table of contents

Understanding the Problem

Intuition

Coding Up The Solution