The Code Talks - Code - Reverse A String

Code - Reverse A String

This problem may seem easy at first like reversing a string one can do by just using any of the pre built functions present with the respective programming language of choice. However what if one is asked to do it a little differently. Maybe by developing our own approach.

How would one go about it? Well there are couple of ways to do it and we have also provided the JAVA code. And if we understand the core logic, we can go ahead and implement in any programming language of our choice. We would be going over the ITERATIVE, CHARACTER ARRAY, STACK/DEQUE, SWAP, RECURSIVE SWAP based approach. Let's deep dive into each of the approach.

ITERATIVE APPROACH

This approach basically plays around the concept that the first character of the original string will be the last character of the reversed string. What we do here is try to fetch each character of the string and keep adding it as a prefix to our reversed string before.

For example if we have a string called as hello. Our string is of length 5 so will iterate from index 0 to index 4. This is how it will go.

Initially reversed string will be empty. Now iterating over the string.

character at index 0 - h.
Appending h as prefix to our reversed string would give us h (since reversed is empty as of now.)
character at index 1 - e.
Appending e as prefix to our reversed string(h) would give us eh
character at index 2 - l.
Appending l as prefix to our reversed string(eh) would give us leh
character at index 3 - l.
Appending l as prefix to our reversed string(leh) would give us lleh
character at index 4 - o.
Appending o as prefix to our reversed string(lleh) would give us olleh which would be our final reversed string.

The code would look something like this in JAVA

public static String iterative(String data) {
        String reversedString = "";
        
        for(int index=0;index<data.length();index++) {
            //get character present at given index in a string
            char charAtIndex = data.charAt(index);
            reversedString = charAtIndex + reversedString;
        }
        
        return reversedString;
    }

CHARACTER ARRAY REVERSE

This approach more is similar to the iterative approach which we used like above. However instead of using charAt(int index) function we are leveraging toCharArray() function which gives us a character array representation of the string we have.

The other difference we have is instead of iterating from the 0th index and adding as a prefix, we can also iterate from the last index and add as a suffix. So for the same example string hello we would

have character array for our string [ h ][ e ][ l ][ l ][ o ]

we would start iterating from backwards i.e. the last index which would be 4 here.

And we would suffix instead of prefix so as per interation it would be o+l+l+e+h which would give us our reversed string olleh.

public static String charArrReverseApproach(String data) {
        String reversedString = "";
        //Convert string to character array
        char[] dataArr = data.toCharArray();
        //Traverse the array backwards and append the string
        for(int index=data.length()-1;index>=0;index--) {
            reversedString = reversedString + dataArr[index];
        }
        
        return reversedString;
    }

We will try to check for below ways to check on reve

STACK / DEQUE BASED

This approach focusses on stack or deque structure which follows the LIFO (Last In First Out) principle. So when we add each character from our string onto the stack / deque and when we remove / pop the item from stack the last character which was added would be removed first.

This is how the stack would look like when we are adding character. As you can see after the last insert the last character would be at the top of the stack.

[h] > [e, h] > [l, e, h] > [l, l, e, h] > [o, l, l, e, h]

Hence when emptying the stack one by one we would be removing the character present in last, second last, third last and so on.. from our original string.

Ultimately giving us the reversed string.

public static String stackBased(String data) {
        String reversedString = "";
        Deque<Character> charDeque = new ArrayDeque<Character>();
        
        //Fill the stack
        for(int index=0;index<data.length();index++) {
            char charAtIndex = data.charAt(index);
            charDeque.push(charAtIndex);
        }
        
        //Empty the stack, following LIFO approach gets us reversed string
        while (!charDeque.isEmpty()) {
            reversedString =  reversedString + charDeque.pop();
        }
        return reversedString;
        
    }

We will try to check for below ways to check on reve

SWAP

While this approach takes the same principle that the first character in the original string will be last, second character would be second last and so on... It takes a more nuanced approach and a more performant when dealing with large strings. What it will do is swap the first with last and will go on until it meets halfway which would `basically mean that the string is reveresed.

public static String swap(String data) {
        char[] dataArr = data.toCharArray();
        char temp;
        //First Position
        int start = 0;
        //Last Position
        int last = data.length()-1;
        

        while(start<=last) {
            //Swap
            temp = dataArr[start];
            dataArr[start] = dataArr[last];
            dataArr[last] = temp;
            
            //Change first and last positions to swap
            last--;
            start++;
        }
        return new String(dataArr);    
    }

RECURSIVE SWAP

This is similar to the swap approach just a more recursive twist to it. Instead of iterating over a loop, it just uses the recursive approach to get to the reversed string value.

public static void recursiveSwap(char[] dataArr, int start, int last) {
        
        if(start>last)
            return;
        
        char temp;
        temp = dataArr[start];
        dataArr[start] = dataArr[last];
        dataArr[last] = temp;
        
        recursiveSwap(dataArr, start+1, last-1);  
/**
         * Do not use start ++ or last -- here.. 
         * Since those are post increment and decrement operator
         * so they will assign which means send the value and then increment it
         * This would basically mean same value 
         * gets sent every time and we would see 
         * stack overflow exception.
         * 
         * You can use ++start --last 
         * which are pre increment/decrement operators
         * 
         */
            
    }

As mentioned in the comment above, ensure that we are not using any post increment or post decrement operators when using recursion calls. Why?? Because you might run into stack overflow errors. And this because of how these operators work.

For example, if we have

 int a = 1;
        int b = a++;
        System.out.println(b);

What do you think the output here will be?? It will 1 because a++ would assign the value to b first which would mean it would assign 1 to b and then increment the value of a to 2. The same would happen in the function call meaning the value would be same every time. And yes, while post increment operators are something that should be avoided. You can use pre increment / decrement operators i.e. ++start, --last would give you expected results.

Well that's about different ways one can go on doing a reverse on string. And an approach in one programming language can be replicated in the other by just changing the required syntax.

That's about the reverse talks for the code. Until next time think about which approach would you choose??