Good day software engineers / developers. Hope your day has started on the right note. Today is Wednesday (hump day). Two more workdays and the weekend will be here.
I have read on different articles that airline traffic in the USA is back to pre COVID-19 pandemic levels. After reading the articles I felt good about the pandemic coming to an end and for the airlines and their employees. That said; I live in a suburb of the Twin Cities of Minneapolis and St. Paul. MSP is an international airport and a hub for several airlines (including Delta). The airport is located next to Bloomington, MN. I used to own a software development company which was based in Bloomington. Every day on my way back home, depending on the wind direction, I could see two lines of six or more airplanes on final to land at MSP. In addition, the city in which I live is very close to a pattern used by planes to land on a third runway at MSP. Depending on the time and wind patterns, we could see several dozen planes around lunch time.
Today you can see a few planes if you spend an hour watching for them to land or after takeoff. By no means, the amount of traffic is close to pre COVID-19 pandemic levels. Being generous I would say that the traffic at MSP is about 10% of what is used to be a couple years ago when the pandemic started. So why are we seeing FAKE NEWS? Is there a presidential election coming up that I have missed? Of course not! In my opinion airlines are so desperate in getting people to vacation this summer, that they might have recruited writers and reporters to spread the need to take a vacation in the USA or better yet in Europe.
For reasons I do not wish to get into at this time, my wife and I decided on a weeklong vacation OUS this summer. We have done this before for the birthday of a good friend. We booked our tickets and hotel via Delta. A week or so we added our two granddaughters that wanted to meet my friend and family and just wanted to relax for a few days.
In the recent weeks we decided that the flights are good, but want to make changes to the accommodations to a different resort. The resort we are currently booked on has a one day policy for cancelation. In other words, you can cancel without penalty if you do so one day before you are scheduled to arrive. Nice!
I have tried to cancel the resort component of our trip using the Delta website. I have tried calling Delta Vacations (800.800.1504) on multiple occasions. A recording states that there are busy. After indicating to do a search on-line, the call disconnects. You cannot wait for an attendant. VERY POOR SERVICE CHOICE DELTA!!!
I have also called General Sales & Services (800.323.2323) on multiple occasions. As I am typing this post, I am holding for about two hours waiting for a representative. After half hour on-hold I hang up.
While waiting I found a different number for International Sales & Service (800.241.241). I will also give it a try. In addition I found on the Delta app on my iPhone Silver Medallion Reservations (800.325.6330) so I called. There was a two-hour wait. I left my phone number. I should be receiving a call from Delta within a couple hours. I placed my call at 13:27 CDT. Will let you know my findings after lunch. It seems that a couple family members from my wife will be joining us today.
We are done with lunch. We usually have lunch around 12:30 CDT, but today it was a couple hours later.
I have not received the call from Delta yet. Believe or not, having to wait for hours allows customers to continue searching the web and finding answers to most of their problems. I found what I needed on-line. I was able to cancel the resort reservations. My wife and I will book on a different resort tomorrow morning. We have stayed at this other resort a few times. The grounds are quite larger and the facilities seem to be newer.
Sorry about so much chit-chat. The main topic for this post is an exercise presented in the YouTube video Dynamic Programming – Learn to Solve Algorithmic Problems & Coding Challenges.
Write a function `canConstruct(target, wordBank)` that accepts a target string and an array of strings. The function should return a boolean indicating whether or not the `target` can be constructed by concatenating element of the `wordBank` array. You may reuse elements of `wordBank` as many times as needed.
We have seen this problem before and solved it using dynamic programming and recursion. The Can Construct post in this blog has the details. At that time we had to add memoization in order to improve performance. This time around we will use Tabulation which is another technique used to solve dynamic programming problems.
The instructor in the video uses the JavaScript programming language. We will use the Java programming language, the VSCode IDE and a Windows 10 computer. You are welcome to use the IDE and platform of choice.
boolean canConstruct(String target, String[] wordBank) {
}
Since we are solving the problem using Java, the signature for the function in question needs to be specified.
ab,abc,cd,def,abcd main <<< target ==><== main <<< wordBank: [ab, abc, cd, def, abcd] main <<< canConstruct: true abcdef ab,abc,cd,def,abcd main <<< target ==>abcdef<== main <<< wordBank: [ab, abc, cd, def, abcd] main <<< canConstruct: true purple purp,p,ur,le,purpl main <<< target ==>purple<== main <<< wordBank: [purp, p, ur, le, purpl] main <<< canConstruct: true skateboard bo,rd,ate,t,ska,sk,boar main <<< target ==>skateboard<== main <<< wordBank: [bo, rd, ate, t, ska, sk, boar] main <<< canConstruct: false enterapotentpot a,p,ent,enter,ot,o,t main <<< target ==>enterapotentpot<== main <<< wordBank: [a, p, ent, enter, ot, o, t] main <<< canConstruct: true eeeeeeeeeeeeeeeeeeeeeeeeeeeeef e,ee,eee,eeee,eeeee,eeeeee main <<< target ==>eeeeeeeeeeeeeeeeeeeeeeeeeeeeef<== main <<< wordBank: [e, ee, eee, eeee, eeeee, eeeeee] main <<< canConstruct: false
The test code expects two input lines. The first contains the target string and the second line a list of strings which should be used to populate the `wordBank` array.
After the arguments are ready, the values are displayed in order to perform a quick and simple check that all is well before we dive into the code for the function in question.
The function in question is called and the returned value is displayed.
Most of the test cases were provided by the instructor. Some were provided for other similar problems.
**** Tabulation Recipe **** 1. Visualize the problem as a table 2. Size the table based on the inputs 3. Initialize the table with some values 4. Seed the trivial answer into the table 5. Iterate through the table 6. Fill further positions based on the current position
Before we get into the code we should take a look at the tabulation recipe so we can follow the steps. That said; the first three steps are not always too obvious.
/**
* 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 target = br.readLine().trim();
// **** read word bank ****
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 function of interest and display result ****
System.out.println("main <<< canConstruct: " + canConstruct(target, wordBank));
}
The test scaffold seems to follow closely the description of the test case processing. I do not have additional comments.
/**
* Write a function `canConstruct(target, wordBank)` that accepts a
* target string and an array of strings.
*
* The function should return a boolean indicating whether or not the
* `target` can be constructed by concatenating element of the
* `wordBank` array.
*
* You may reuse elements of `wordBank` as many times as needed.
*
* m = target.length
* n = wordBack.length
*
* Time: O(m^2 * n) Space: O(m)
*/
static boolean canConstruct(String target, String[] wordBank) {
// **** sanity checks ****
if (target.length() == 0) return true;
// **** initialization (using boolean because function returns boolean) ****
boolean table[] = new boolean[target.length() + 1];
table[0] = true;
// **** iterate through the table ****
for (int i = 0; i < table.length; i++) {
// **** skip this position in the table (if needed) ****
if (table[i] == false)
continue;
// **** loop through the word bank ****
for (int j = 0; j < wordBank.length; j++) {
// **** for ease of use ****
String word = wordBank[j];
// **** if out of bounds (skip) ****
if (i + word.length() >= table.length)
continue;
// **** for ease of use ****
String sub = target.substring(i, i + word.length());
// **** check if this word matches (set table entry to true) ****
if (sub.equals(word))
table[i + word.length()] = true;
}
// **** if target was found (early return true) ****
if (table[target.length()])
return true;
}
// **** return last entry in table ****
return table[target.length()];
}
We start by performing a sanity check. If the target string is blank, then we can return true. The reason is that you can always return a blank string regardless of the strings in the `wordBank`.
We then initialize the table. We need to figure out the type, length and values that will be inserted. In this case, since we need to return a Boolean value, our table is of type Boolean. The size will be the length of the target string plus one. This will allow us to align the values and simplify operations. We also initialize the first entry in the table to true.
Now we need to iterate on the table. We need to use previous values and the strings from the `wordBank` in order to update values in the table.
If the current entry in the table is false it implies that it will not contribute to the solution. We skip this entry.
Now we need to process the `wordBank` in order to update the table entries. If a word allows us to move on the table forward we set entries to true.
We extract the next word and determine if it can be used to update an entry in the table. If not we skip it.
We then generate a string with the sub string extracted from the target. If the sub string matches the contents of the word we update the corresponding table entry.
After processing each position in the table we check if the last entry has been set to true. If so we have found a combination and are able to return true.
If we do not exit at this time, we continue processing the rest of the positions in the table. When all is set and done, if the last entry remains with a value of false then we cannot construct the target string; otherwise we can and our function returns true.
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