I haven't touched algorithm for almost 3 years. When I first saw this question, I was like, "This is easy. I am going to get it. This is easy, right?". So, I tried to solve it with my understanding and I am so ashamed that I couldn't get it run within 1o mins. I remembered it needs to have a temp holder to hold the first value and stuff like that, but I barely can remember what it was. After some time of trying, I decided to view the solution and realized that I have totally forgotten about what I learned earlier! It was the classic two pointer method question!

Anyway, here's the simplest solution to this question. Oh, by the way, it requires modifying the array in place and seems like this is the best solution.

public void reverseString(char[] s){
    int i = 0, j = s.length - 1;
    while(i < j){
        char temp = s[i];
        s[i] = s[j];
        s[j] = temp;
        i++;
        j--;
    }
}

There you have it! It is a simple iterative index value swapping. What about doing it recursively?

public void reverseString(char[] s) {
    helper(0, s.length - 1, s);        
}

private static void helper(int start, int end, char[] s){
    if(s == null || start >= end ){
        return;
    }
    char ch = s[start];
    s[start] = s[end];
    s[end] = ch;
    helper(start + 1, end - 1, s);
}

So, the idea is that we swap the first and last character in the char array, then we move both pointers one step towards each other. Once the start pointer meets with the end pointer, we will end it there as there is no more swapping needed at this point.

I hope this question might be good warmup for you. Thanks for reading!

Post was published on 25 Feb 2019, last updated on 2 Mar 2019.

Like the content? Support the author by paypal.me!