This short week after Memorial Day seems to be flying by. I have not been outside today yet, but the day looks quite nice. The high for today is 87F. Somewhat low when comparing to what is expected for the next three days: 92F, 94F and 91F.
The cleaning lady typically comes on Fridays. She will be here today Thursday around 09:30 AM. Not sure if the nice weekend has affected her plans.
As I have previously mentioned, I move to the dark side when I decided to get an iPhone instead of an Android cell phone. My Google Pixel 4 phone died with less than two years of service. The actual phone looks like I just purchased it. I like to keep my cell phones in good shape so they are as reliable as possible. A day or two before my Pixel phone dies, the Pixel 4 phone of my daughter in law dies in a similar way. My son lives in a different city about five miles from us. What a coincidence!!!
So far I like my new phone and watch. I can do a lot of things from the watch without having to access the phone. The watch displays a lot of information that I like to have readily available (i.e., temperature, heart rate and to top it off it has access to Siri).I spoke with my wife a few minutes ago. It seems that the cleaning lady will not be coming today or tomorrow due to personal issues. Wonder if the nice weather had something to do with it.
One last thing, while getting ready to publish this post I found out that this blog has reached 8,000 subscribers. Thank you a lot, I appreciate your support. I am targeting 10,000 subscribers in order to make a switch from WordPress to YouTube. If you wish to express your opinion please leave a message bellow. I will take it into account!
If you follow this blog, we are in the middle of working with the dynamic programming problems in Dynamic Programming – Learn to Solve Algorithmic Problems & Coding Challenges in YouTube. The video is by freeCodeCamp.org and the instructor is Alvin. He is very good at presenting the materials. I like that he repeats the concepts using different examples. In my opinion repetition is very important for learning.
Write a function `countConstruct(target, wordBank)` that accepts a target string and an array of strings. The function should return the number of ways that the `target` can be constructed by concatenating elements of the `wordBank` array. You may reuse elements of `wordBank` as many times as needed.
In this problem we are given a target string and a string[] array of words. Our mission is to return the count of ways in which we can construct the target string from the words in the bank. As you can see this is similar to Can Construct.
Alvin uses JavaScript in the YouTube video. In this post we will use instead the Java programming language with the VSCode IDE and will develop the code in a Windows 10 computer. If I am not mistaken Alvin uses a Macintosh notebook from Apple.
int countConstruct(String target, String[] wordBank) {
}
The signature for the function of interest is quite simple. We are given a target string which we need to construct using the words in the string[] array which is the second argument to the function.
abcdef
ab,abc,cd,def,abcd
main <<< target ==>abcdef<==
main <<< wordBank: [ab, abc, cd, def, abcd]
main <<< countConstruct: 1
main <<< time: 1 ms.
<<< memo: {ef=0, def=1, abcdef=1, cdef=0}
main <<< countConstructMemo: 1
main <<< time: 1 ms.
purple
purp,p,ur,le,purpl
main <<< target ==>purple<==
main <<< wordBank: [purp, p, ur, le, purpl]
main <<< countConstruct: 2
main <<< time: 1 ms.
<<< memo: {e=0, ple=1, le=1, purple=2, urple=1}
main <<< countConstructMemo: 2
main <<< time: 1 ms.
skateboard
bo,rd,ate,t,ska,sk,boar
main <<< target ==>skateboard<==
main <<< wordBank: [bo, rd, ate, t, ska, sk, boar]
main <<< countConstruct: 0
main <<< time: 0 ms.
<<< memo: {teboard=0, ard=0, eboard=0, ateboard=0, skateboard=0, d=0, board=0}
main <<< countConstructMemo: 0
main <<< time: 0 ms.
enterapotentpot
a,p,ent,enter,ot,o,t
main <<< target ==>enterapotentpot<==
main <<< wordBank: [a, p, ent, enter, ot, o, t]
main <<< countConstruct: 4
main <<< time: 0 ms.
<<< memo: {t=1, pot=2, enterapotentpot=4, ot=2, entpot=2, apotentpot=4, otentpot=4, potentpot=4, erapotentpot=0, tentpot=2}
main <<< countConstructMemo: 4
main <<< time: 1 ms.
eeeeeeeeeeeeeeeeeeeeeeeeeeeeef
e,ee,eee,eeee,eeeee,eeeeee
main <<< target ==>eeeeeeeeeeeeeeeeeeeeeeeeeeeeef<==
main <<< wordBank: [e, ee, eee, eeee, eeeee, eeeeee]
main <<< countConstruct: 0
main <<< time: 12500 ms.
<<< memo: {eeeeeeeeeeeeeeeeeeef=0, eeeeeeeeeeeeeeeef=0, eeeeeeef=0, eef=0, eeeeeeeeeeeeeeeeeeeeeeef=0, eeeeeeeeeeeeeeeeeeeeeeeeeeef=0, eeeeeeeeeeef=0, eeeeeeeeeeeeeeeeeeeeeeeeeeeeef=0, eeeeeeeeeeeeeeeeef=0, eeeeeeeeeeeeeeeeeeeeeeeeeef=0, eeeeeeeeeeeeeef=0, eeeef=0, eeeeeeeeef=0, eeeeeeeeeeeeeeef=0, ef=0, eeeeeeeeeeeeef=0, eeeeeeeef=0, f=0, eeeeeeeeeeeef=0, eeeeeeeeeeeeeeeeeeeeeef=0, eeeeeef=0, eeef=0, eeeeeeeeeeeeeeeeeef=0, eeeeeeeeeeeeeeeeeeeeeeeeeeeef=0, eeeeeeeeeeeeeeeeeeeeeeeeef=0, eeeeef=0, eeeeeeeeeeeeeeeeeeeef=0, eeeeeeeeeeeeeeeeeeeeeeeef=0, eeeeeeeeeef=0, eeeeeeeeeeeeeeeeeeeeef=0}
main <<< countConstructMemo: 0
main <<< time: 2 ms.
Our test scaffold is given two input lines. The first contains the target string. The second line holds the words to be included in the bank.
Our test scaffold displays the values of the two arguments before calling the function of interest.
Note that we first call the function that does not make use of memoization. After calling the second implementation which uses memoization, the contents of the data structure used for memoization is displayed. The result of the function follows.
It seems that the results from the two implementations of the function of interest match. That is good news.
In the first few examples all is well and the first function is returning the results in a reasonable amount of time.
Please take a look at the last example. The function without memoization takes about 12.5 seconds to execute. The implementation with memoization takes a couple of milliseconds. This makes it imperative to implement memoization.
/**
* Test scaffold.
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** initialization ****
long start = 0;
long end = 0;
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read target string ****
String target = br.readLine().trim();
// **** read word bank String[] ****
String[] wordBank = br.readLine().trim().split(",");
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< target ==>" + target + "<==");
System.out.println("main <<< wordBank: " + Arrays.toString(wordBank));
// **** call the function and display result ****
start = System.currentTimeMillis();
System.out.println("main <<< countConstruct: " + countConstruct(target, wordBank));
end = System.currentTimeMillis();
System.out.println("main <<< time: " + (end - start) + " ms.");
// **** call the function and display result ****
start = System.currentTimeMillis();
System.out.println("main <<< countConstructMemo: " + countConstructMemo(target, wordBank));
end = System.currentTimeMillis();
System.out.println("main <<< time: " + (end - start) + " ms.");
}
The test code seems to match closely to the description about processing the test cases. I will not add to it at this time.
/**
* Write a function `countConstruct(target, wordBank)` that accepts a
* target string and an array of strings.
*
* The function should return the number of ways that the `target` can
* be constructed by concatenating elements of the `wordBank` array.
*
* You may reuse elements of `wordBank` as many times as needed.
*
* Recursive call without memoization.
*
* m = target.length
* n = wordBack.length
* Time: O(n^m * m) Space: O(m^2)
*/
static int countConstruct(String target, String[] wordBank) {
// **** base case(s) ****
if (target.length() == 0) return 1;
// **** initialization ****
int count = 0;
// **** loop through all the words in the bank ****
for (String word : wordBank) {
// **** determine if this word is a prefix ****
if (target.indexOf(word) == 0) {
// **** for ease of use ****
String prefix = word;
// **** generate suffix ****
String suffix = target.substring(prefix.length());
// **** make recursive call and update count ****
count += countConstruct(suffix, wordBank);
}
}
// **** return count ****
return count;
}
This is the recursive call without memoization.
First we check for the base case.
We then initialize the count that the function will return.
We are now ready to loop once per word in the bank.
We check if the current word is a suffix for the current target string. If so we compute the suffix using the current word as a prefix.
We are now ready to make a recursive call.
Note that the result of the recursive call is added to the count.
After finishing processing all words the function returns the count.
The approach should make sense if you draw a recursion tree for an example. If you feel you need additional help, take a look at the video when dealing with this example. It is about 02:45:00 into the video.
As we can tell by the last test case, the recursive call without memoization is too slow. We need to add memoization.
/**
* Write a function `countConstruct(target, wordBank)` that accepts a
* target string and an array of strings.
*
* The function should return the number of ways that the `target` can
* be constructed by concatenating elements of the `wordBank` array.
*
* You may reuse elements of `wordBank` as many times as needed.
*
* Entry point for recursive call with memoization.
*
* m = target.length
* n = wordBack.length
* Time: O(n * m^2) Space: O(m^2)
*/
static int countConstructMemo(String target, String[] wordBank) {
// **** sanity check(s) ****
if (target.length() == 0) return 0;
// **** initiaization ****
HashMap<String, Integer> memo = new HashMap<>();
// **** start recursion and get count ****
int count = countConstructMemo(target, wordBank, memo);
// ???? ????
System.out.println("<<< memo: " + memo.toString());
// **** return count ****
return count;
}
This is the entry point for the recursive call that uses memoization. The approach is quite common.
We may start with a sanity check. This is not needed but if we hit the specific case it may save us a fraction of a second.
We then initialize the data structure that we will use to store the memoization information. In this case we want to associate a string with a count.
We then start the recursion process. Note that the call is quite similar but in this case we need to pass on the memoization data structure.
To help understanding how memoization works in the test cases, we display the contents of the memoization hash map.
Finally we return the count.
**** Memoization Tasks **** 1. Select a data structure to store key-value pairs of interest. 2. Pass as an argument to the recursive call the memoization data structure. 3. Make a copy of the recursive call without memoization and edit it. 4. Check if the key-value pair is in the memoization data structure. If found, return the associate value. 5. Recursively call the modified recursive call making sure the memoization data structure is passed as an argument. 6. Before terurning the result, make sure to store it in the proper key-value pair. 7. Test your code!!!
This is a list of steps that we should follow when using memoization.
Make sure you check out the recursive call edited for memoization and verify that all the steps listed above are present and make sense.
/**
* Recursive call with memoization.
*/
static private int countConstructMemo( String target,
String[] wordBank,
HashMap<String, Integer> memo) {
// **** base case(s) ****
if (memo.containsKey(target)) return memo.get(target);
if (target.length() == 0) return 1;
// **** initialization ****
int count = 0;
// **** loop through all the words in the bank ****
for (String word : wordBank) {
// **** determine if this word is a prefix ****
if (target.indexOf(word) == 0) {
// **** for ease of use ****
String prefix = word;
// **** generate suffix ****
String suffix = target.substring(prefix.length());
// **** make recursive call and update count ****
count += countConstructMemo(suffix, wordBank, memo);
}
}
// **** memoize this result ****
memo.put(target, count);
// **** return count ****
return count;
}
This is the recursive call with memoization added.
We start by copying the original recursive call without memoization and then edit it as needed following the steps previously describe.
The new function with memoization is simple to edit. We just need to check for a key-value, make the recursive call with the memo, and finally store the new key-value pair.
Hope this recipe makes sense. The key is to choose the proper key-value pair based on the situation. In this case we map a string to the count used as a value.
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