<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Jason Wei on Medium]]></title>
        <description><![CDATA[Stories by Jason Wei on Medium]]></description>
        <link>https://medium.com/@jasonwei_613?source=rss-2aa431f5a97b------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*n7FeiJxfLsmAYUjU</url>
            <title>Stories by Jason Wei on Medium</title>
            <link>https://medium.com/@jasonwei_613?source=rss-2aa431f5a97b------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sat, 21 Nov 2026 07:39:56 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@jasonwei_613/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Java Reverse String (Recursion)]]></title>
            <link>https://medium.com/@jasonwei_613/java-reverse-string-recursion-f3dcaa3d90e2?source=rss-2aa431f5a97b------2</link>
            <guid isPermaLink="false">https://medium.com/p/f3dcaa3d90e2</guid>
            <category><![CDATA[tutorial]]></category>
            <category><![CDATA[problem-solving]]></category>
            <category><![CDATA[recursion]]></category>
            <category><![CDATA[java]]></category>
            <category><![CDATA[leetcode-easy]]></category>
            <dc:creator><![CDATA[Jason Wei]]></dc:creator>
            <pubDate>Tue, 21 May 2019 05:11:00 GMT</pubDate>
            <atom:updated>2019-05-21T05:11:00.917Z</atom:updated>
            <content:encoded><![CDATA[<p>I decided to use Medium as a place to record some of my solutions for LeetCode. One of the reason is to remind myself if I ever forget how to solve them another is I hope someone will be able to learn from it. I’ll be using different languages for different question, but most of the time the logic of solving the problem is transferable.</p><p>So the first question is Reversing a given character array using recursion. The question specifically state not to return the array, but to modify it.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/750/1*tJzX9fBWl6ALiN94cbzIHw.jpeg" /></figure><p>Following is the example given by <a href="http://leetcode.com/">leetcode.com</a></p><p><strong>Example 1:</strong></p><pre><strong>Input: </strong>[&quot;h&quot;,&quot;e&quot;,&quot;l&quot;,&quot;l&quot;,&quot;o&quot;]<br><strong>Output: </strong>[&quot;o&quot;,&quot;l&quot;,&quot;l&quot;,&quot;e&quot;,&quot;h&quot;]</pre><p><strong>Example 2:</strong></p><pre><strong>Input: </strong>[&quot;H&quot;,&quot;a&quot;,&quot;n&quot;,&quot;n&quot;,&quot;a&quot;,&quot;h&quot;]<br><strong>Output: </strong>[&quot;h&quot;,&quot;a&quot;,&quot;n&quot;,&quot;n&quot;,&quot;a&quot;,&quot;H&quot;]</pre><h3><strong>Solution:</strong></h3><pre>class Solution {<br>  public void reverseString(char[] s) {<br>     helper(0,s);<br>  }<br>  private void helper(int index, char[]s){<br>     if(index &gt;= s.length-index-1 || s== null){<br>     return;<br>     }<br>     char temp = s[index];<br>     s[index]=s[s.length-index-1];<br>     s[s.length-index-1] = temp;<br>     helper(1+ index, s);<br>   }<br>  }<br>}</pre><p>The general idea of the solution is to swap the first and last, second with second to last etc. A few things to note:</p><p><strong>Index : </strong>the index of the item that’s being swap to the back</p><p><strong>s.length-index -1 : </strong>the index of the item that’s being swap to the front</p><p>Here’s what happens when the code is run:</p><p><strong>First Function Call</strong></p><p>[“a”,”b”,”c”,”d”] (index =0, s.length -index- 1 = 3)</p><p>[“d”,”b”,”c”,”a”] the result of first function call and it’s put into the helper function again</p><p><strong>Second Function Call</strong></p><p>[“d”, “b”, “c”, “a”] (index =1, s.length-index-1 =2)</p><p>[“d”, “c”, “b”, “a”]</p><p><strong>Third Function Call</strong></p><p>[“d”, “c”, “b”, “a”] (index = 2, s.length-index-1 = 1) since the index is larger then the s.length-index-1 the function returns.</p><h3><strong>Process</strong></h3><p>Now that we know how the code works, let’s look into the process of solving the problem.</p><h4>Goal</h4><p>The most important thing for solving anything is to understand what you need to solve. In this case is to reverse the items in the given character array using recursion. No return is necessary, just modify the array.</p><h4><strong>Identifying Cases</strong></h4><p>For me the first step of solving something with recursion is to define the possible cases that we’ll encounter. In this scenario:</p><ol><li>Null array is passed in</li><li>Array with one item</li><li>Array with two items</li><li>Array with three or more</li></ol><h4><strong>Identifying Base Case</strong></h4><p>Then from here we identify the base case. The base case is the condition that just returns a value without making a call of the function. Usually this defines the bottom of the recursion. For example, in the problem if there’s a null array passed in you can’t do anything with the null array, because no matter how many times you call the helper function you’ll still get a null array. Therefore we write an if statement to set the base of recursion. It’s like saying “Hey this is the bottom, you can’t do anything now. You can only return and go back up one step.”</p><p>Now you are probably wondering why I didn’t say array with one item is also a base case. To be honest it is, and I actually did put it in the base case validation but in a different way, let’s come back to it.</p><h4><strong>Even Number of Item</strong></h4><p>In the event of having even numbers of item, the one being swap to the back and the one being swap to the front will never land on the same index, which mean we can’t write something like:</p><pre>if(index == s.length-index-1)...</pre><p>We’ll need to figure out what’s the pattern for even number of items to make it apply to more cases. When we have even number of items, this means that when we swap until they are in the middle the one being swap to the back and the one being swap to the front will be side by side. This means that they are one index apart, if we were to continue the swapping, the index that started from zero will be larger than the index that started from the length of array minus one; we want to avoid this. Having start index and end index crossover each other means it’ll end up swapping everything back. So to add this case to the condition check we’ll have:</p><pre>if(index &gt; s.length-index-1 || index ==null)....</pre><p>This way we cover the base case of having no(null) item, two item and any even number of items.</p><h4><strong>Odd Number of Item</strong></h4><p>In the previous section we said <strong>index </strong>parameter is the index of the item that’s being swap to the back of the array and the <strong>s.length-index -1 </strong>is the item that is being swap to the front. Going back to the #2 the one item case if there is only one item that means the index is zero, the length of the array is one. So when the length minus the index minus one will give us zero. This means that the item that’s being swap to the front and the item that is being swap to the back is the same item. Therefor your function won’t need to do anything, which we can have:</p><pre>if(index &gt;= s.length-index-1 || index ==null)....</pre><p>Since when we have odd numbers of items, the swapping will end up landing in the middle of the whole array. So the checking if the index and s.length-index-1 will apply to all of the odd number of items.</p><p>Up to this point we’ve touch on the base case of null(zero) item, one item, two item, any number of odd or even number of items.</p><h4><strong>Solving the problem</strong></h4><p>Now this is the fun part, and sometimes can be the most challenging part. We need to figure how to swap the items in the array so it’s reversed. Since null item, one item is already taken care of by the base case, we can just look at the next smallest amount of item — array with two items.</p><p>Looking at #3 the array with two items, it’ll only require one function call. So to solve this we use:</p><ul><li>a temporary variable to save the first item</li><li>replace the original first item in the array with the last item in the array</li><li>replace the original last item in the array with the item stored in the temporary variable</li></ul><p>So this is what we have so far:</p><pre>private void helper(int index, char[]s){<br>     if(index &gt;= s.length-index-1 || s== null){<br>     return;<br>     }<br>     char temp = s[index];<br>     s[index]=s[s.length-index-1];<br>     s[s.length-index-1] = temp;<br>   }<br>  }<br>}</pre><h4><strong>Adding the recursive function call</strong></h4><p>We have one case left to solve. Case #4 three or more items in an array. Since three is an odd number it’s already solved by the code we have above, but it doesn’t solve any higher number of items. Since we know that we are swapping the items in the array repeatedly, we can add in the recursive call in the end:</p><pre>private void helper(int index, char[]s){<br>     if(index &gt;= s.length-index-1 || s== null){<br>     return;<br>     }<br>     char temp = s[index];<br>     s[index]=s[s.length-index-1];<br>     s[s.length-index-1] = temp;<br>     helper(1+ index, s);<br>   }<br>  }</pre><p>This way, starting from the zero index, every time a swap is done the mutated array is then pass in to the same helper function with index moved forward one to continue the swap until one of the base condition is met.</p><p>That’s it for this problem, feel free to comment if you have any questions or suggestions.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f3dcaa3d90e2" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>