It is shortly after 05:00 AM in the Twin Cities of Minneapolis and St. Paul. The temperature is just under 32F. It should go up a few degrees as the day progresses. In reality I am at 68F in my office and not planning on leaving the house today.
I mentioned in a previous post that I had ordered from Amazon three books which would be delivered today Tuesday. The first arrived last Sunday, the second arrived yesterday Monday and just before going to bed I noticed a message from Amazon indicating that I should reorder the third book from a different reseller. One of the books was delivered at my home the second must have been dropped in my mailbox. Will check it at lunch time (after what I said, I guess I will leave the house for a few minutes), and I believe I have to look for the third book again.
I decided to work on the LeetCode 1324 problem named Print Words Vertically.
Given a string s. Return all the words vertically in the same order in which they appear in s. Words are returned as a list of strings, complete with spaces when is necessary. (Trailing spaces are not allowed). Each word would be put on only one column and that in one column there will be only one word. Constraints: o 1 <= s.length <= 200 o s contains only upper case English letters. o It's guaranteed that there is only one space between 2 words.
The problem’s title appears to call for our solution to print to the console, but it seems we need to return the results on a list so it would be easier for LeetCode to check the results.
Given a string, we need to separate it into words and then traverse the same position on each word putting it in a data structure so we can generate the results. Note that we cannot include trailing spaces. This will become clear when we take a look at some examples. LeetCode provides three examples. I believe they illustrate well what needs to be done.
I will be solving this problem using Java in a Windows 10 machine and the VSCode IDE. Due to this, I will have to generate a test scaffold to read the input string, pass it to the method in questions and then display the results. When done with my method I will copy it to the LeetCode IDE and run it. It is easier to just develop the code on-line using the IDE provided by LeetCode.
class Solution {
public List<String> printVertically(String s) {
}
}
The signature for our method is as expected. We are given a string in which all the words are IN UPPER CASE and separated by a single space.
HOW ARE YOU main <<< s ==>HOW ARE YOU<== main <<< str ==>HAY<== main <<< str ==>ORO<== main <<< str ==>WEU<== main <<< str ==>HAY<== main <<< str ==>ORO<== main <<< str ==>WEU<== TO BE OR NOT TO BE main <<< s ==>TO BE OR NOT TO BE<== main <<< str ==>TBONTB<== main <<< str ==>OEROOE<== main <<< str ==> T<== main <<< str ==>TBONTB<== main <<< str ==>OEROOE<== main <<< str ==> T<== CONTEST IS COMING main <<< s ==>CONTEST IS COMING<== main <<< str ==>CIC<== main <<< str ==>OSO<== main <<< str ==>N M<== main <<< str ==>T I<== main <<< str ==>E N<== main <<< str ==>S G<== main <<< str ==>T<== main <<< str ==>CIC<== main <<< str ==>OSO<== main <<< str ==>N M<== main <<< str ==>T I<== main <<< str ==>E N<== main <<< str ==>S G<== main <<< str ==>T<== I LIKE CHEESE AND CRACKERS main <<< s ==>I LIKE CHEESE AND CRACKERS<== main <<< str ==>ILCAC<== main <<< str ==> IHNR<== main <<< str ==> KEDA<== main <<< str ==> EE C<== main <<< str ==> S K<== main <<< str ==> E E<== main <<< str ==> R<== main <<< str ==> S<== main <<< str ==>ILCAC<== main <<< str ==> IHNR<== main <<< str ==> KEDA<== main <<< str ==> EE C<== main <<< str ==> S K<== main <<< str ==> E E<== main <<< str ==> R<== main <<< str ==> S<== I ENJOY CRACKERS AND CHEESE main <<< s ==>I ENJOY CRACKERS AND CHEESE<== main <<< str ==>IECAC<== main <<< str ==> NRNH<== main <<< str ==> JADE<== main <<< str ==> OC E<== main <<< str ==> YK S<== main <<< str ==> E E<== main <<< str ==> R<== main <<< str ==> S<== main <<< str ==>IECAC<== main <<< str ==> NRNH<== main <<< str ==> JADE<== main <<< str ==> OC E<== main <<< str ==> YK S<== main <<< str ==> E E<== main <<< str ==> R<== main <<< str ==> S<==
I believe that the first three examples came from LeetCode.
Our test scaffolding seems to read the input line and display it.
The method in question seems to be called and the results displayed. It also seems that a second implementation of the method is called and the results are also displayed.
In the first example we have three words each with three characters so there are no spaces we need to take into consideration.
On the second example, note that we do not include spaces after the ‘T’. Such trailing spaces are not allowed.
At this point, I would like to suggest trying to solve the problem on your own before looking at my solution. If after a few minutes of trying you get stuck, then continue reading looking for inspiration (hints). As soon as you get an idea, stop reading and continue with your approach. When solving a problem, hints are useful to proceed (we are working on the same team), but copying a solution is useless because you would be relegating the problem as memorization which is not learning.
/**
* Test scaffold.
*
* !!! NOT PART OF SOLUTION !!!
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read string ****
String s = br.readLine().trim();
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< s ==>" + s + "<==");
// **** generate solution ****
List<String> lst = printVertically1(s);
// **** display result ****
for (String str : lst)
System.out.println("main <<< str ==>" + str + "<==");
System.out.println();
// **** generate solution ****
lst = printVertically(s);
// **** display result ****
for (String str : lst)
System.out.println("main <<< str ==>" + str + "<==");
}
Our test scaffolding is NOT PART OF THE SOLUTION. We use a buffered reader to read the input line. After closing the buffered reader we invoke a version of the method in question and display the results. A second implementation, which is quite similar to the first, is then invoked. The results are then displayed.
/**
* Return all the words vertically in the same order in which they appear in s.
*
* Runtime: 1 ms, faster than 87.78% of Java online submissions.
* Memory Usage: 37.5 MB, less than 72.16% of Java online submissions.
*/
static List<String> printVertically1(String s) {
// **** sanity checks ****
if (s == null || s.length() == 0)
return null;
// **** initialization ***
char ch;
// **** split words ****
String[] words = s.split(" ");
// **** ****
int L = words.length;
// **** ****
int N = 0;
for (int i = 0; i < L; i++) {
if (words[i].length() >= N)
N = words[i].length();
}
// **** declare and initialize array of string builders ****
StringBuilder[] sba = new StringBuilder[N];
for (int i = 0; i < N; i++)
sba[i] = new StringBuilder();
// **** loop once per character position ****
for (int i = 0; i < N; i++) {
// **** pick a char from each word ****
for (int j = 0; j < L; j++) {
// **** get next character from this word ****
if (i < words[j].length())
ch = words[j].charAt(i);
else
ch = ' ';
// **** append character to string builder ****
sba[i].append(ch);
}
}
// **** populate list ****
List<String> lst = new ArrayList<String>();
for (int i = 0; i < sba.length; i++)
lst.add(sba[i].toString().stripTrailing());
// **** return list ****
return lst;
}
We start by performing sanity checks and declare a variable.
We then split the words into an array. We traverse the words array to get the length of the longest word.
We declare and initialize an array of string builders. We could have just dealt with strings but they are immutable to manipulating them is not as efficient as to using string builders.
We then enter a nested loop. The outer loop is used to pick the letter from each word at the same position. The inner loop is used to append the characters in different string builders. If a word is shorter than the current index, we use a space instead of a character from the word. We append the space or character to the string builder.
When all is set and done we need to generate strings and add them to a list to return. We declare the list and append the string representation removing trailing spaces.
We then return the list.
/**
* Return all the words vertically in the same order in which they appear in s.
*
* Runtime: 1 ms, faster than 87.78% of Java online submissions.
* Memory Usage: 36.9 MB, less than 99.15% of Java online submissions.
*/
static List<String> printVertically(String s) {
// **** sanity checks ****
if (s == null || s.length() == 0)
return null;
// **** initialization ****
int wordCount = 0;
int maxLength = 0;
List<StringBuilder> sbl = null;
// **** split string into words ****
String[] words = s.split(" ");
// **** get the word count ****
wordCount = words.length;
// **** set the max length and index ****
for (int i = 0; i < words.length; i++) {
if (words[i].length() >= maxLength)
maxLength = words[i].length();
}
// **** initialize array list of string builders ****
sbl = new ArrayList<>(maxLength);
for (int i = 0; i < maxLength; i++)
sbl.add(new StringBuilder());
// **** loop once per word ****
for (int i = 0; i < wordCount; i++) {
// **** current word ****
String w = words[i];
// **** put each character in a consecutive string builder ****
for (int j = 0; j < w.length(); j++) {
StringBuilder sb = sbl.get(j);
sb.append(w.charAt(j));
}
// **** append blanks (as needed) ****
if (w.length() < maxLength) {
for (int j = w.length(); j < maxLength; j++) {
StringBuilder sb = sbl.get(j);
sb.append(' ');
}
}
}
// **** populate list ****
List<String> lst = new ArrayList<>();
for (int i = 0; i < maxLength; i++)
lst.add(sbl.get(i).toString().stripTrailing());
// **** return list ****
return lst;
}
This started as a different approach, but ended into something quite similar to the previous implementation.
I am not going to go into much detail because the code is similar to the previous implementation. The execution time is quite similar.
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, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. 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.
One last thing, many thanks to all 6,851 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy. I believe we can all see the light at the end of the tunnel.
Regards;
John
john.canessa@gmail.com