It is Saturday morning in the Twin Cities of Minneapolis and St. Paul. According to the forecast today is going to be a scorcher. The temperature will rise to 97F. I live in a suburb of the Twin Cities. Typically the city of Minneapolis gets at least a couple more degrees higher.
Yesterday my wife and I went to the Mall of America which is located in the city of Bloomington. On our way back home the temperature was 102F.
Given the hot spell we are experiencing in this part of the country, this morning my wife and I had breakfast and headed out for a walk. When we got back I was perspiring. After a nice shower I headed down to my office to get in a 2-hour block of work.
Tomorrow Sunday presidential elections will be held in Peru. There are two candidates. One is an open communist and terrorist and the other is pro democracy. Hopefully the elections will favor the right. Politically and economically South America is slowly falling to communism and the economies of most (never generalize) are getting worse by the day. Will see what happens tomorrow during election day.
Enough chit-chat; let’s get down to business.
As you can see by reading the last few posts I have been watching the YouTube video Dynamic Programming – Learn to Solve Algorithmic Problems & Coding Challenges and experimenting with the examples. Alvin, the instructor, is very good at what he does. If you are interested in learning or just brushing up on dynamic programming, the video is worth watching.
Write a function `allConstruct(String target, String[] wordBank)` that accepts a target string and an array of strings. The function should return a 2D array containing all of the ways that the `target` can be constructed by concatenating elements of the `wordBank` array. Each element of the 2D array should represent one combination that constructs the `target`. You may reuse elements of `wordBank` as many times as needed.
This is the last of a sequence of similar problems. In each problem, the inputs are the same, but what is requested is different. This problem is the most complex one in the series.
The author uses the JavaScript programming language. I am using Java and the VSCode IDE running on a Windows 10 computer. In Java arrays cannot be resized. Because of this fact, the arguments will remain as suggested by the problem, but instead of return the results in a two dimensional array, we will use a List<List<String>> instead.
allConstruct('', [cat,dog,mouse]) -> [[]]
allConstruct(hello, [cat,dog,mouse]) -> []
When dealing with dynamic programming there is always a recursive function. Recursive functions require a base case. In this problem we have two cases to consider. In the first one when we reach the condition in which we have an answer. In other words we found a set (might be empty) that can be used to construct the target string. In the second case, we were not able to get a subset of words from the bank to generate the target string.
As I mentioned, the instructor in the video uses the JavaScript programming language. In this post we will be using the Java programming language and the VSCode IDE on a Windows 10 platform. If I am not mistaken the author use and Apple notebook.
List<List<String>> allConstruct(String target, String[] wordBank) {
}
I took the liberty too change the signature of the function in question. In the original description our solution needs to return a 2D array. In Java we probably want to use lists. If push comes to shove we can always convert the List<List<String>> to a 2D array. I will leave that as an exercise.
hello
cat,dog,mouse
main <<< target ==>hello<==
main <<< wordBank: [cat, dog, mouse]
main <<< ll: [[]]
main <<< allConstruct: []
main <<< time: 0 ms.
<<< memo: {hello=[]}
main <<< allConstructMemo: []
main <<< time: 1 ms.
cat,dog,mouse
main <<< target ==><==
main <<< wordBank: [cat, dog, mouse]
main <<< ll: [[]]
main <<< allConstruct: [[]]
main <<< time: 0 ms.
main <<< allConstructMemo: [[]]
main <<< time: 0 ms.
purple
purp,p,ur,le,purpl
main <<< target ==>purple<==
main <<< wordBank: [purp, p, ur, le, purpl]
main <<< ll: [[]]
main <<< allConstruct: [[purp, le], [p, ur, p, le]]
main <<< time: 1 ms.
<<< memo: {purple=[[purp, le], [p, ur, p, le]]}
main <<< allConstructMemo: [[purp, le], [p, ur, p, le]]
main <<< time: 1 ms.
abcdef
ab,abc,cd,def,abcd,ef,c
main <<< target ==>abcdef<==
main <<< wordBank: [ab, abc, cd, def, abcd, ef, c]
main <<< ll: [[]]
main <<< allConstruct: [[ab, cd, ef], [ab, c, def], [abc, def], [abcd, ef]]
main <<< time: 0 ms.
<<< memo: {abcdef=[[ab, cd, ef], [ab, c, def], [abc, def], [abcd, ef]]}
main <<< allConstructMemo: [[ab, cd, ef], [ab, c, def], [abc, def], [abcd, ef]]
main <<< time: 0 ms.
skateboard
bo,rd,ate,t,ska,sk,boar
main <<< target ==>skateboard<==
main <<< wordBank: [bo, rd, ate, t, ska, sk, boar]
main <<< ll: [[]]
main <<< allConstruct: []
main <<< time: 0 ms.
<<< memo: {skateboard=[]}
main <<< allConstructMemo: []
main <<< time: 1 ms.
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaz
a,aa,aaa,aaaa,aaaaa
main <<< target ==>aaaaaaaaaaaaaaaaaaaaaaaaaaaaaz<==
main <<< wordBank: [a, aa, aaa, aaaa, aaaaa]
main <<< ll: [[]]
main <<< allConstruct: []
main <<< time: 11326 ms.
<<< memo: {aaaaaaaaaaaaaaaaaaaaaaaaaaaaaz=[]}
main <<< allConstructMemo: []
main <<< time: 11224 ms.
Our test scaffold reads the first two lines from a test case. The first line contains the target string and the second the words in the `wordBank`.
After reading the values and creating the variables, the values are displayed. I like to do so to make sure all is well before I start dealing with the problem at hand.
Since we are dealing with Java I want to make sure that the proper value is returned in the end case when we have a solution. As you can see there are several incorrect ways to generate the proper value.
We then call two implementations of the function in question. The execution times are displayed following the returned values. The first implementation is based on a recursive call without memoization. The second is based on a recursive call with memoization.
If you look at the last test case, you will see that both implementations take about the same time. We will get to that shortly.
Also note that before returning the results for the recursive function with memoization we also display the contents of the data structure we used to store key-value pairs.
/**
* Test scaffold
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** initialization ****
long start = 0;
long end = 0;
List<List<String>> ans = null;
// **** open a buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read the target string ****
String target = br.readLine().trim();
// **** read the readBank String[] ****
String[] wordBank = br.readLine().trim().split(",");
// **** close the buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< target ==>" + target + "<==");
System.out.println("main <<< wordBank: " + Arrays.toString(wordBank));
// ???? ????
List<List<String>> ll = new ArrayList<>(Arrays.asList(new ArrayList<>()));
System.out.println("main <<< ll: " + ll.toString());
// ???? ????
ll = new ArrayList<List<String>>();
// System.out.println("main <<< ll: " + ll.toString());
// ???? ????
List<ArrayList<String>> lol = new ArrayList<ArrayList<String>>();
// System.out.println("main <<< lol: " + lol.toString());
// ???? ????
ArrayList<ArrayList<String>> lofl = new ArrayList<ArrayList<String>>();
// System.out.println("main <<< lofl: " + lofl.toString());
// **** generate the list for the specified target and word bank ****
start = System.currentTimeMillis();
ans = allConstruct(target, wordBank);
end = System.currentTimeMillis();
// **** display answer ****
System.out.println("main <<< allConstruct: " + ans.toString());
System.out.println("main <<< time: " + (end - start) + " ms.");
// **** generate the list for the specified target and word bank ****
start = System.currentTimeMillis();
ans = allConstructMemo(target, wordBank);
end = System.currentTimeMillis();
// **** display answer ****
System.out.println("main <<< allConstructMemo: " + ans.toString());
System.out.println("main <<< time: " + (end - start) + " ms.");
}
The test code starts by initializing three variables. The first two are used to time the functions of interest. The third is used to collect the result returned by the function implementations. We could just have displayed the returned value directly; but I decided to first store it and then display it. Of course in production this would not be suggested or needed.
Our test code reads the two input lines and displays the values of the associated variables that have been created and populated.
We then display the returned value when a set of strings match a target. Note that only the first one works. If you have questions regarding this in Java, the simplest thing is to do an internet search and find the answer. This is not part of the solution.
We then make the calls to the two implementations of the function in question.
/**
* Write a function `allConstruct(String target, String[] wordBank)`
* that accepts a target string and an array of strings.
*
* The function should return a 2D array containing all of the ways
* that the `target` can be constructed by concatenating elements of
* the `wordBank` array. Each element of the 2D array should represent
* one combination that constructs the `target`.
*
* You may reuse elements of `wordBank` as many times as needed.
*
* Recursive call without memoization.
*
* m = =target.length
* n = wordBank.length
*
* Time: O(n^m) Space: O(m)
*/
static List<List<String>> allConstruct(String target, String[] wordBank) {
// **** base case(s)****
if (target.length() == 0) return new ArrayList<>(Arrays.asList(new ArrayList<>()));
// **** initialization ****
List<List<String>> result = new ArrayList<>();
// **** loop through the word bank making a recursive call (if needed) ****
for (String word : wordBank) {
// **** recursive call (if word is a prefix of target) ****
if (target.indexOf(word) == 0) {
// **** generate suffix for target ****
String suffix = target.substring(word.length());
// **** make recursive call ****
List<List<String>> suffixWays = allConstruct(suffix, wordBank);
// **** ****
List<List<String>> targetWays = new ArrayList<>();
// **** add prefix to the head of each list ****
for (int i = 0; i < suffixWays.size(); i++) {
// **** create a new list ****
List<String> tmp = new ArrayList<>(suffixWays.get(i));
// **** add preffix to this list ****
tmp.add(0, word);
// **** add this list to this list of lists ****
targetWays.add(tmp);
}
// **** add lists to result ****
for (int i = 0; i < targetWays.size(); i++)
result.add(new ArrayList<>(targetWays.get(i)));
}
}
// **** return all possible combinations ****
return result;
}
This code represents the recursive call without memoization.
We start by checking the base case that signals if a set of strings in the bank match the target string.
Next we initialize the result.
As in previous implementations, we loop through all the words in the bank.
If the current word is a suffix for our target string we need to process it and make a recursive call; otherwise we just ignore it and move to the next word (if any).
If the current word is a suffix, we extract it for ease of use.
We then make a recursive call that returns a list of list of suffixes.
We need to loop through the returned list adding at the start of each list the current word from the bank. After adding the word we add the updated list into the `targetWays` list of lists.
We are then ready to add the `targetWays` list of lists to the result list of list.
After we are done we return the result list of lists which can be empty if we did not find a set of words in the bank that could be used to generate the target string.
If you have some doubts on how this function works, you might want to single step though the code or add some statements to see how the lists are being populated.
You should note that we have to process all the words in the bank at least once or in some cases multiple times (see last test case) in order to make sure we return all possible combinations.
/**
* Write a function `allConstruct(String target, String[] wordBank)`
* that accepts a target string and an array of strings.
*
* The function should return a 2D array containing all of the ways
* that the `target` can be constructed by concatenating elements of
* the `wordBank` array. Each element of the 2D array should represent
* one combination that constructs the `target`.
*
* You may reuse elements of `wordBank` as many times as needed.
*
* Recursive call with memoization.
*
* m = =target.length
* n = wordBank.length
*
* Time: O(n^m) Space: O(m)
*/
static List<List<String>> allConstructMemo(String target, String[] wordBank) {
// **** sanity check(s) ****
if (target.length() == 0) return new ArrayList<>(Arrays.asList(new ArrayList<>()));
// **** initialization ****
HashMap<String, List<List<String>>> memo = new HashMap<>();
// **** recursive call ****
List<List<String>> ans = allConstructMemo(target, wordBank, memo);
// ???? ????
System.out.println("<<< memo: " + memo.toString());
// **** return ans ****
return ans;
}
This is the entry point for the recursive implementation using memoization.
We start by performing a sanity check. In some cases this avoids making additional calls. If a function / method is called with frequency, your solution might save a considerable amount of time.
We then declare and initialize a hash map to be used to store key-value pairs for memoization.
We start the recursive process.
When done we would like to see the contents of the hash map.
Finally we return the associated answer. This approach is quite standard and should be familiar at this point.
/**
* Recursive call with memoization.
*/
static List<List<String>> allConstructMemo( String target,
String[] wordBank,
HashMap<String, List<List<String>>> memo) {
// **** base case(s)****
if (memo.containsKey(target)) return memo.get(target);
if (target.length() == 0) return new ArrayList<>(Arrays.asList(new ArrayList<>()));
// **** initialization ****
List<List<String>> result = new ArrayList<>();
// **** loop through the word bank making a recursive call (if needed) ****
for (String word : wordBank) {
// **** recursive call (if word is a prefix of target) ****
if (target.indexOf(word) == 0) {
// **** generate suffix for target ****
String suffix = target.substring(word.length());
// **** make recursive call ****
List<List<String>> suffixWays = allConstruct(suffix, wordBank);
// **** ****
List<List<String>> targetWays = new ArrayList<>();
// **** add prefix to the head of each list ****
for (int i = 0; i < suffixWays.size(); i++) {
// **** create a new list ****
List<String> tmp = new ArrayList<>(suffixWays.get(i));
// **** add preffix to this list ****
tmp.add(0, word);
// **** add this list to this list of lists ****
targetWays.add(tmp);
}
// **** add lists to result ****
for (int i = 0; i < targetWays.size(); i++)
result.add(new ArrayList<>(targetWays.get(i)));
}
}
// **** save the key-value pair ****
memo.put(target, result);
// **** return all possible combinations ****
return result;
}
We start by checking the base cases. The first case is due to the use of memoization. It is worthwhile to check if the key-value pair has been encountered before.
The rest of the code is quite similar to the original recursive call implementation without memoization. Note that when we make the recursive call we must pass the memo for memoization.
Once we are done processing all the words in the bank, we save the current result in the hash map and as before return the result.
As you can see the bulk of the work is done removing prefixes from the target word. The run time with and without memoization are the same. This is why our last example is as fast with as it is without memoization.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John