Good day!!! Hope your day is going well. The day started relatively cold at 58F with relative humidity around 93%. The weather, according to my iPhone, was fair. My wife and I did our daily morning walk as soon as we were done with breakfast. On my way back I usually water the plans, but due to the weather conditions, I decided to skip. I will water them tomorrow morning.
In my previous post Can Construct – Tabulation I was not please with the telephone support provided by Delta Airlines. They offer a callback when you are waiting to speak with a representative. For example, a callback was promised while being informed that the wait was about 3-hours long. The callback would be received about 12 hours latter; sometimes in the middle of the night.
It is a fact that airlines were hit hard with the COVID-19 pandemic. Most of them (never generalize) let go a large part of their staff. In the past few weeks things are starting to return to normal with customer service at Delta. Earlier this week I placed a call to change several things on a reservation. There was a delay of about two hours (2:15). I requested a callback and as usual wrote the time I expected a representative to call me. About two hours later, Ronda from Delta called. She was very pleasant. She spent a lot of time (15 minutes or so) to make all the changes I requested. Not only that, but she suggested alternatives that could save me some money and make the travelling experience better. Felt like service was back to pre COVID-19 pandemic. Great job Ronda!!!
You probably have heard of competitive programming. It seems that software engineers need to solve a problem as soon as possible. Sounds good, but imagine if you go for a surgery and the surgeon wants to perform the procedure in the least amount of time. Not sure about you, but I would prefer someone with experience that takes its time and wants to produce the best results, not just finish faster than others. Seems to me like a compromise between quality and time. That said; I will try my first competition on Saturday. Will let you know my findings. Perhaps I will change my opinion.
As you know, I have been watching the Dynamic Programming – Learn to Solve Algorithmic Problems & Coding Challenges video by freeCodeCamp.org. This is the last post related to the video. I finished watching it and experimenting with the problems / exercises. I had a good time and learned a lot.
Write a function `allConstruct(target, 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. You may reuse elements of the `wordBank` as many times as needed.
This problem is similar to All Construct which we solve at the beginning of this month. At the time we used a recursive approach. After trying some problems, due to performance, we decided to include Memoization. In the current pass, we will solve the same problem but will be using Tabulation. The article Tabulation vs. Memoization by GeeksforGeeks provides a simple description of the two approaches used to solve dynamic programs.
In the problem at hand, we need to return a 2D array of strings with the possible combinations that can be used to generate the `target` string.
As mentioned earlier, the on-line instructor uses JavaScript to solve the problem. We will use Java, the VSCode IDE on a Windows 10 computer.
String[][] allConstruct(String target, String[] wordBank) {
}
The signature for the function in question in Java expects a target string and an array of words that we can use to generate the target string.
We need to generate test code to collect the input for the `target` and the `wordBank`. We then will call the function of interest and display the results. Hopefully they will meet our expectations and match the results obtained by the instructor. Spoiler alert; they do!
cat,dog main <<< target ==><== length: 0 main <<< wordBank: [cat, dog] main <<< ans: [ [] ] birds cat,dog main <<< target ==>birds<== length: 5 main <<< wordBank: [cat, dog] <<< table: [[[]], [], [], [], [], []] size: 6 main <<< ans: [ ] abcdef ab,abc,cd,def,abcd,ef,c main <<< target ==>abcdef<== length: 6 main <<< wordBank: [ab, abc, cd, def, abcd, ef, c] <<< table: [[[]], [], [], [], [], [], []] size: 7 <<< table: [[[]], [], [[ab]], [], [], [], []] size: 7 <<< table: [[[]], [], [[ab]], [[abc]], [], [], []] size: 7 <<< table: [[[]], [], [[ab]], [[abc]], [[abcd]], [], []] size: 7 <<< table: [[[]], [], [[ab]], [[abc]], [[abcd], [ab, cd]], [], []] size: 7 <<< table: [[[]], [], [[ab]], [[abc], [ab, c]], [[abcd], [ab, cd]], [], []] size: 7 <<< table: [[[]], [], [[ab]], [[abc], [ab, c]], [[abcd], [ab, cd]], [], [[abc, def], [ab, c, def]]] size: 7 <<< table: [[[]], [], [[ab]], [[abc], [ab, c]], [[abcd], [ab, cd]], [], [[abc, def], [ab, c, def], [abcd, ef], [ab, cd, ef]]] size: 7 main <<< ans: [ [abc, def] [ab, c, def] [abcd, ef] [ab, cd, ef] ] abcdef ab,abc,cd,def,abcd,ef,c,a,b,d,e,f main <<< target ==>abcdef<== length: 6 main <<< wordBank: [ab, abc, cd, def, abcd, ef, c, a, b, d, e, f] <<< table: [[[]], [], [], [], [], [], []] size: 7 <<< table: [[[]], [], [[ab]], [], [], [], []] size: 7 <<< table: [[[]], [], [[ab]], [[abc]], [], [], []] size: 7 <<< table: [[[]], [], [[ab]], [[abc]], [[abcd]], [], []] size: 7 <<< table: [[[]], [[a]], [[ab]], [[abc]], [[abcd]], [], []] size: 7 <<< table: [[[]], [[a]], [[ab], [a, b]], [[abc]], [[abcd]], [], []] size: 7 <<< table: [[[]], [[a]], [[ab], [a, b]], [[abc]], [[abcd], [ab, cd], [a, b, cd]], [], []] size: 7 <<< table: [[[]], [[a]], [[ab], [a, b]], [[abc], [ab, c], [a, b, c]], [[abcd], [ab, cd], [a, b, cd]], [], []] size: 7 <<< table: [[[]], [[a]], [[ab], [a, b]], [[abc], [ab, c], [a, b, c]], [[abcd], [ab, cd], [a, b, cd]], [], [[abc, def], [ab, c, def], [a, b, c, def]]] size: 7 <<< table: [[[]], [[a]], [[ab], [a, b]], [[abc], [ab, c], [a, b, c]], [[abcd], [ab, cd], [a, b, cd], [abc, d], [ab, c, d], [a, b, c, d]], [], [[abc, def], [ab, c, def], [a, b, c, def]]] size: 7 <<< table: [[[]], [[a]], [[ab], [a, b]], [[abc], [ab, c], [a, b, c]], [[abcd], [ab, cd], [a, b, cd], [abc, d], [ab, c, d], [a, b, c, d]], [], [[abc, def], [ab, c, def], [a, b, c, def], [abcd, ef], [ab, cd, ef], [a, b, cd, ef], [abc, d, ef], [ab, c, d, ef], [a, b, c, d, ef]]] size: 7 <<< table: [[[]], [[a]], [[ab], [a, b]], [[abc], [ab, c], [a, b, c]], [[abcd], [ab, cd], [a, b, cd], [abc, d], [ab, c, d], [a, b, c, d]], [[abcd, e], [ab, cd, e], [a, b, cd, e], [abc, d, e], [ab, c, d, e], [a, b, c, d, e]], [[abc, def], [ab, c, def], [a, b, c, def], [abcd, ef], [ab, cd, ef], [a, b, cd, ef], [abc, d, ef], [ab, c, d, ef], [a, b, c, d, ef]]] size: 7 <<< table: [[[]], [[a]], [[ab], [a, b]], [[abc], [ab, c], [a, b, c]], [[abcd], [ab, cd], [a, b, cd], [abc, d], [ab, c, d], [a, b, c, d]], [[abcd, e], [ab, cd, e], [a, b, cd, e], [abc, d, e], [ab, c, d, e], [a, b, c, d, e]], [[abc, def], [ab, c, def], [a, b, c, def], [abcd, ef], [ab, cd, ef], [a, b, cd, ef], [abc, d, ef], [ab, c, d, ef], [a, b, c, d, ef], [abcd, e, f], [ab, cd, e, f], [a, b, cd, e, f], [abc, d, e, f], [ab, c, d, e, f], [a, b, c, d, e, f]]] size: 7 main <<< ans: [ [abc, def] [ab, c, def] [a, b, c, def] [abcd, ef] [ab, cd, ef] [a, b, cd, ef] [abc, d, ef] [ab, c, d, ef] [a, b, c, d, ef] [abcd, e, f] [ab, cd, e, f] [a, b, cd, e, f] [abc, d, e, f] [ab, c, d, e, f] [a, b, c, d, e, f] ] purple purp,p,ur,le,purpl main <<< target ==>purple<== length: 6 main <<< wordBank: [purp, p, ur, le, purpl] <<< table: [[[]], [], [], [], [], [], []] size: 7 <<< table: [[[]], [], [], [], [[purp]], [], []] size: 7 <<< table: [[[]], [[p]], [], [], [[purp]], [], []] size: 7 <<< table: [[[]], [[p]], [], [], [[purp]], [[purpl]], []] size: 7 <<< table: [[[]], [[p]], [], [[p, ur]], [[purp]], [[purpl]], []] size: 7 <<< table: [[[]], [[p]], [], [[p, ur]], [[purp], [p, ur, p]], [[purpl]], []] size: 7 <<< table: [[[]], [[p]], [], [[p, ur]], [[purp], [p, ur, p]], [[purpl]], [[purp, le], [p, ur, p, le]]] size: 7 main <<< ans: [ [purp, le] [p, ur, p, le] ] skateboard bo,rd,ate,t,ska,sk,boar main <<< target ==>skateboard<== length: 10 main <<< wordBank: [bo, rd, ate, t, ska, sk, boar] <<< table: [[[]], [], [], [], [], [], [], [], [], [], []] size: 11 <<< table: [[[]], [], [], [[ska]], [], [], [], [], [], [], []] size: 11 <<< table: [[[]], [], [[sk]], [[ska]], [], [], [], [], [], [], []] size: 11 <<< table: [[[]], [], [[sk]], [[ska]], [], [[sk, ate]], [], [], [], [], []] size: 11 <<< table: [[[]], [], [[sk]], [[ska]], [[ska, t]], [[sk, ate]], [], [], [], [], []] size: 11 <<< table: [[[]], [], [[sk]], [[ska]], [[ska, t]], [[sk, ate]], [], [[sk, ate, bo]], [], [], []] size: 11 <<< table: [[[]], [], [[sk]], [[ska]], [[ska, t]], [[sk, ate]], [], [[sk, ate, bo]], [], [[sk, ate, boar]], []] size: 11 main <<< ans: [ ] aaaaaaaaaaz a,aa,aaa,aaaa,aaaaa main <<< target ==>aaaaaaaaaaz<== length: 11 main <<< wordBank: [a, aa, aaa, aaaa, aaaaa] <<< table: [[[]], [], [], [], [], [], [], [], [], [], [], []] size: 12 main <<< ans: [ ]
The first two test cases check end conditions. Let’s take an in depth look at the third test case.
The first input line represents the `target` string. The second input line represents the words that we will put in our `wordBank` and will use to build the `target` string. Note that our function of interest needs to return all possible combinations.
It seems that our test code reads the two input lines, allocates and populates the variables and then displays them. This is done to verify that all is well before entering the function in question that we need to develop
The lines that follow illustrate the contents of the table used to solve the problem using memoization. They are there to show us progress. We do not need to display the contents of the table to solve the problem.
When our function completes, the results are displayed. The display is a 2D array in which each line represents a combination of words that result in the `target` string. In this case it seems that there are four ways to generate `abcdef`.
In the last example, I turned off (commented out) the statement that displays the contents of the table. The table grew too big to be displayed. You can run the problem with the debug statement enabled to appreciate what was displayed.
**** Tabulation Recipe **** 1. Visualize the problem as a table (determine data type) 2. Size the table based on the inputs 3. Initialize the table with some values (determine base case) 4. Seed the trivial answer into the table 5. Iterate through the table 6. Fill further positions based on the current position
When approaching a dynamic programming problem using tabulation, we may follow this six-step recipe. It is a good recipe but there is some thinking that needs to be done.
**** Dynamic Programming Approach **** 1. Notice any overlapping subproblems 2. Decide what is the trivially smallest input (i.e., base case) 3. Think recursively to use Memoization 4. Think iteratively to use Tabulation 5. Define a strategy first!!!
After the last problem was completed, the instructor provided some additional insights as to how to approach a dynamic problem using memoization.
The steps are well known, but they vary with each problem. There is no free lunch!
/**
* Test scaffold.
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read target string ****
String target = br.readLine().trim();
// **** read word bank array ****
String[] wordBank = br.readLine().trim().split(",");
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< target ==>" + target + "<== length: " + target.length());
System.out.println("main <<< wordBank: " + Arrays.toString(wordBank));
// **** call function of interest ****
String[][] ans = allConstruct(target, wordBank);
// **** display 2D array ****
if (ans == null)
System.out.println("main <<< ans: []");
else {
System.out.println("main <<< ans:\n[");
for (int i = 0; i < ans.length; i++)
System.out.println(Arrays.toString(ans[i]));
System.out.println("]");
}
}
The test code for our problem seems to follow the description of the test cases. We read the input lines, populate the necessary variables, call the function of interest and display results.
/**
* Write a function `allConstruct(target, wordBank)` that accepts a
* target string and ann 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.
*
* You may reuse elements of the `wordBank` as many times as needed.
*
* m = target.length
* n = wordBank.length
*
* Time: O(n^m) Space: O(n^m)
*/
static String[][] allConstruct(String target, String[] wordBank) {
// **** sanity check(s) [[]]****
if (target.length() == 0) {
String[][] ans = new String[1][1];
ans[0] = new String[] {""};
return ans;
}
// **** create and initialize table ****
ArrayList<ArrayList<ArrayList<String>>> table = new ArrayList<ArrayList<ArrayList<String>>>();
for (int i = 0; i < target.length() + 1; i++)
table.add(i, new ArrayList<ArrayList<String>>());
ArrayList<ArrayList<String>> lol = table.get(0);
lol.add(new ArrayList<String>());
// ???? ????
System.out.println("<<< table: " + table.toString() + " size: " + table.size());
// **** iterate through the table ****
for (int i = 0; i < table.size(); i++) {
// **** get to the current list of lists ****
lol = table.get(i);
// **** if blank entry (skip) ****
if (lol.size() == 0)
continue;
// **** iterate through the word bank ****
for (int j = 0; j < wordBank.length; j++) {
// **** for ease of use ****
String word = wordBank[j];
// **** generate index ****
int ndx = i + word.length();
// **** if we can NOT extract prefix from target (skip) ****
if (ndx > target.length())
continue;
// **** extract prefix from the target ****
String prefix = target.substring(i, ndx);
// **** if word and prefix do NOT match (skip) ****
if (!word.equals(prefix))
continue;
// **** source list of lists ****
ArrayList<ArrayList<String>> src = table.get(i);
// **** destination list of lists ****
ArrayList<ArrayList<String>> dst = table.get(ndx);
// **** copy source list(s) to this table entry ****
for (int k = 0; k < src.size(); k++) {
// **** source list to copy ****
ArrayList<String> srcLst = src.get(k);
// **** destination list ****
ArrayList<String> dstLst = new ArrayList<String>();
// **** add source to destination list ****
dstLst.addAll(srcLst);
// **** append word to destination list ****
dstLst.add(word);
// **** add destination list to destinaltion list of lists ****
dst.add(dstLst);
}
// ???? ????
System.out.println("<<< table: " + table.toString() + " size: " + table.size());
}
}
// **** get last list of lists in table ****
ArrayList<ArrayList<String>> ansLst = table.get(target.length());
// **** 2D array to hold answer ****
String[][] ans = new String[ansLst.size()][];
// **** traverse the list of lists ****
for (int i = 0; i < ansLst.size(); i++) {
// **** get this array list ****
ArrayList<String> al = ansLst.get(i);
// **** generate array from array list ****
String[] arr = al.toArray(String[]::new);
// **** insert array into 2D array ****
ans[i] = arr;
}
// **** return 2D array ****
return ans;
}
We start by performing a sanity check.
We create and initialize the table. In this case our table is implemented as an ArrayList<ArrayList<ArrayList<String>>>. The actual table is represented by the leftmost array list. Each entry in the table contains a list of lists. The lists in such list represent the word combinations that in the last entry of our table should be all the combinations possible to generate the `target` `abcdef` word.
I first tried using arrays, but the code got complicated so I switched to array lists.
The process is similar to what we have done in other problems. We create a table and initialize it.
We then traverse all the entries in the table in ascending order.
For each entry we visit all the words in the `wordBank` array.
If there is a match we update table entries to the right of our table.
When all is said and done, the contents of the last entry in our table should contain all the possible combinations that can be generated to match the `target` string using the contents of the specified `wordBank`.
Since the problem requires us to return a 2D array of strings, we need to convert the last ArrayList<ArrayList<String>> collection to a 2D array of strings. This is accomplished with the code past the main loop.
Towards the end of the video the instructor mentioned the Coderbyte site. I visited the site and noted that I already had an account. In the next few days will spend some time experimenting with some problems presented there.
I believe that Java was not the best choice for solving the problems in the YouTube video. Besides JavaScript I believe Python would have been a good choice.
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