Good day. Hope your day has started on the right note. I had a combination of good and not so good news. Such is life. We need to learn how to deal with both and grow stronger and smarter.
Today we will take a look at LeetCode 344 Reverse String which is ranked as Easy by HackerRank.
Write a function that reverses a string. The input string is given as an array of characters s. Constraints: o 1 <= s.length <= 105 o s[i] is a printable ascii character. Follow up: Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.
We are given a char[] `s` and need to reverse the contents of it.
Let’s see if we can generate a single solution that meets the requirements in the Follow up section.
We will be solving this problem using the Java programming language and the VSCode IDE on a Windows computer. We will need to implement a test scaffold which is not necessary if you use the on-line IDE provided by LeetCode. Since we will not use the on-line IDE, we need to generate a piece of code that will read the input line, create and populate the char[] `s`, call the function of interest and display the output. Note that the test scaffold IS NOT PART OF THE SOLUTION!
public void reverseString(char[] s) {
}
The signature for the function of interest uses a single argument which is the char[] `s`. Note that the changes to the char[] `s` must end up in `s` since our function does not return a char[].
"h","e","l","l","o" main <<< s: [h, e, l, l, o] <<< l: 0 r: 4 <<< l: 1 r: 3 main <<< output: [o, l, l, e, h] "H","a","n","n","a","h" main <<< s: [H, a, n, n, a, h] <<< l: 0 r: 5 <<< l: 1 r: 4 <<< l: 2 r: 3 main <<< output: [h, a, n, n, a, H] "x" main <<< s: [x] main <<< output: [x]
The first line of each test case holds a String[] which our test scaffold needs to convert into a char[]. Once that is accomplished, our test scaffold displays the contents of char[] `s` in order to make sure all is well before calling the function of interest.
Our function of interest displays some lines that are used to help us understand the algorithm. Please note that such output IS NOT PART OF THE SOLUTION.
The last output line displays the output which should be equal to the input argument but with the characters in reversed order. All three cases seem to comply with the requirements.
/**
* Test scaffold.
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read input into char[] s ****
char[] s = Arrays.stream(br.readLine().trim().split("\",\"|\""))
.collect(Collectors.joining())
.toCharArray();
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< s: " + Arrays.toString(s));
// **** call function of interest ****
reverseString(s);
// **** display output ****
System.out.println("main <<< output: " + Arrays.toString(s));
}
Our test scaffold, which IS NOT PART OF THE SOLUTION, seems to perform the tasks described when we covered the test cases. I do not have much to add at this point in time.
/**
* Write a function that reverses a string.
*
* Runtime: 1 ms, faster than 96.35% of Java online submissions.
* Memory Usage: 45.7 MB, less than 82.94% of Java online submissions.
*
* 477 / 477 test cases passed.
* Status: Accepted
* Runtime: 1 ms
* Memory Usage: 45.7 MB
*
* Runtime: O(n) - Space: O(1)
*/
static public void reverseString(char[] s) {
// **** sanity check(s) ****
if (s.length == 1) return;
// **** initialization ****
int l = 0;
int r = s.length - 1;
// **** loop inverting array ****
while (l < r) {
// ???? ????
System.out.println("<<< l: " + l + " r: " + r);
char tmp = s[l];
s[l++] = s[r];
s[r--] = tmp;
}
}
We start the function of interest by performing a sanity check.
The initialization step sets the left and the right indices in order to get ready to start the loop.
In each pass of the loop we swap the characters pointed by `l` and `r`. Note that the indices are respectively incremented and decremented.
In the comments section we can see the performance values associated with this implementation.
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