Good day! Hope your day has started on the right note. Earlier today I participated in a video call using Zoom. I have avoided using Zoom due to security issues. Today I had to install it in order to participate in the call. It seems that the look and feel has improved considerably. Will read more about security issues in the past few months. One way or the other, after the call ended, I removed the application from my Windows computer.
I was chatting with a software engineer and the idea of replacing the garbage collector in Java came up. In general you would replace it if it is not keeping up with the task (i.e., too many requests when processing IoT calls). I am aware and have done it using C and C++. After completing this post I will spend an hour researching more on this subject.
Earlier today I looked at the next problem in the series that I have been working on LeetCode. The problem at hand is LeetCode 557 Reverse Words in a String III. We will attempt to solve the problem using the Java programming language and the VSCode IDE on a Windows machine. If you solve the problem using the on-line IDE provided by LeetCode, you will not be needing a test scaffold to read the input data, populate the proper variable(s), call the function of interest passing the necessary argument(s) and then displaying the result. In our case we will generate a simple test scaffold. Please note that the test code IS NOT PART OF THE SOLUTION.
Given a string s, reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order. Constraints: o 1 <= s.length <= 5 * 104 o s contains printable ASCII characters. o s does not contain any leading or trailing spaces. o There is at least one word in s. o All the words in s are separated by a single space. Related Topics: o Two Pointers o String
We are given a string and we need to reverse the characters in the words while leaving alone the white spaces.
public String reverseWords(String s) {
}
Since we are solving the problem using Java the signature for the function of interest seems to require a single argument and it needs to return the reversed string. Makes sense.
Let's take LeetCode contest main <<< s ==>Let's take LeetCode contest<== <<< arr: [L, e, t, ', s, , t, a, k, e, , L, e, e, t, C, o, d, e, , c, o, n, t, e, s, t] <<< b: 0 e: 5 <<< arr: [s, ', t, e, L, , t, a, k, e, , L, e, e, t, C, o, d, e, , c, o, n, t, e, s, t] <<< b: 6 e: 10 <<< arr: [s, ', t, e, L, , e, k, a, t, , L, e, e, t, C, o, d, e, , c, o, n, t, e, s, t] <<< b: 11 e: 19 <<< arr: [s, ', t, e, L, , e, k, a, t, , e, d, o, C, t, e, e, L, , c, o, n, t, e, s, t] <<< b: 20 e: 27 <<< arr: [s, ', t, e, L, , e, k, a, t, , e, d, o, C, t, e, e, L, , t, s, e, t, n, o, c] main <<< output ==>s'teL ekat edoCteeL tsetnoc<== God Ding main <<< s ==>God Ding<== <<< arr: [G, o, d, , D, i, n, g] <<< b: 0 e: 3 <<< arr: [d, o, G, , D, i, n, g] <<< b: 4 e: 8 <<< arr: [d, o, G, , g, n, i, D] main <<< output ==>doG gniD<== 012 4567 9 main <<< s ==>012 4567 9<== <<< arr: [0, 1, 2, , 4, 5, 6, 7, , 9] <<< b: 0 e: 3 <<< arr: [2, 1, 0, , 4, 5, 6, 7, , 9] <<< b: 4 e: 8 <<< arr: [2, 1, 0, , 7, 6, 5, 4, , 9] <<< b: 9 e: 10 <<< arr: [2, 1, 0, , 7, 6, 5, 4, , 9] main <<< output ==>210 7654 9<== a main <<< s ==>a<== <<< arr: [a] <<< b: 0 e: 1 <<< arr: [a] main <<< output ==>a<==
We have several test cases. I believe the first two came directly from LeetCode.
Our test scaffold needs to read the input string and populate the variable `s` with the input. The test code seems to display the input string to make sure all is well so far before calling the function of interest.
The next few lines display information that is used to help us understand how the algorithm that we decided on works. Please note that such output IS NOT PART OF THE SOLUTION.
The last line displays the output for the specific test case. You can verify that the characters in the words have been reversed keeping the spaces in place.
/**
* Test scaffold
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read string `s` ****
String s = br.readLine().trim();
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< s ==>" + s + "<==");
// **** call function of interest and display output ****
System.out.println("main <<< output ==>" + reverseWords(s) + "<==");
}
Our test scaffold opens a buffered reader, reads the input string, closes the buffered reader, displays the input string, calls the function of interest with the `s` variable, and finally displays the output. NOt much to add at this point in time.
/**
* Reverse the order of characters in each word within a sentence
* while still preserving whitespace and initial word order.
*
* Using String Builder.
*
* 29 / 29 test cases passed.
* Status: Accepted
* Runtime: 3 ms
* Memory Usage: 39.8 MB
*/
static public String reverseWords0(String s) {
// **** initialization ****
int from = 0;
int len = s.length();
StringBuilder sb = new StringBuilder();
StringBuilder word = null;
// **** loop reversion words - O(n) ****
while (from < len) {
// **** index of next ' ' ****
int space = s.indexOf(' ', from);
// **** extract word to reverse ****
if (space != -1)
word = new StringBuilder(s.substring(from, space));
else
word = new StringBuilder(s.substring(from));
// **** reverse word ****
word.reverse();
// **** append reversed word ****
sb.append(word);
// **** append space (if needed) ****
if (space != -1) sb.append(' ');
// **** update index ****
if (space != -1)
from = space + 1;
else
from = len;
}
// **** return string with reversed words ****
return sb.toString();
}
In this first implementation of the function of interest we will use a couple string builders. One will hold the output string while the other will be used to reverse each word.
We enter a loop that will finish when the from index gets to the end of the input string.
We start by looking for the next space in the string `s`. We then extract the next word. We reverse the word. We append the reversed word to the string builder. If needed we append a blank character. Lastly we update the index where the next word starts.
After the loop is done, we need to return the string associated with the string builder.
Note that this solution uses two string builders.
The comment section of the function shows the performance of this solution. Not bad, but perhaps we could do somewhat better.
/**
* Reverse the order of characters in each word within a sentence
* while still preserving whitespace and initial word order.
*
* Using char[].
*
* 29 / 29 test cases passed.
* Status: Accepted
* Runtime: 2 ms
* Memory Usage: 39.7 MB
*
* Runtime: O(n) - Space: O(n)
*/
static public String reverseWords(String s) {
// **** initialization ****
char[] arr = s.toCharArray();
int len = s.length();
int b = 0;
int e = 0;
// ???? ????
System.out.println("<<< arr: " + Arrays.toString(arr));
// **** loop selecting words to reverse - O(n) ****
while (b < len) {
// **** look for end of current word ****
for (e = b; e < len && arr[e] != ' '; e++);
// ???? ????
System.out.println("<<< b: " + b + " e: " + e);
// **** reverse the word ****
reverse(arr, b, e - 1);
// ???? ????
System.out.println("<<< arr: " + Arrays.toString(arr));
// **** update index ****
b = e + 1;
}
// **** return string associated with the arr ****
return String.valueOf(arr);
}
We start by performing some initialization steps. Note that we generate a char[] with the contents of the characters in the input string `s`.
We will loop through the char[] array.
We then get the index for the end of the word which is managed by the `e` variable. At this point we know the start and end indices for the current word.
We call the reverse() auxiliary function which reverses the characters of the current word.
Finally we update the index that flags the beginning of the next word.
After the loop completes, we return the string representation of the char[] `arr`.
/**
* Auxiliary function.
*/
static public void reverse(char[] arr, int b, int e) {
while(b < e) {
char tmp = arr[b];
arr[b++] = arr[e];
arr[e--] = tmp;
}
}
This is the auxiliary function that reverses the characters specified by the two indices.
This function is slightly faster than the previous one. Could we improve on this last implementation? We could see if we could optimize by using a string builder. I will leave that as an exercise for the ambitious.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
Please note that the code here presented might not be the best possible solution. In most cases, after solving the problem, you can take a look at the best accepted solution provided by the different websites (i.e., HackerRank, LeetCode).
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.
Enjoy;
John