Solution by rohitnandi12


  • 1
    R

    Primary Thougths
    There are multiple approaches to solve this problem. If you are thinking of using a library function, that will do but will not help you in the long run. Ask yourself, Do you want to be a script kiddie rest of your life or be a hard core developer?

    Test Cases
    Try to create your own test cases. You can take help of the interviewer, to validate your understanding of the problem.

    Test Inputs
    T1 : ""         // output : ""
    T2 : "   "      // output : "   "
    T3 : "Rotator"  //output : "rotatoR"
    

    Approach #1 Using a Data Structure

    Intuition

    Since the first character needs to be printed last and last character first. It resembles to me as FILO = First In and Last Out. Data structure which holds such property is Stack, which will do the work.

    Algorithm

    • Initialize a stack buff
    • Push all the characters in string s to buff
    • Pop all the characters from buff and append to a StringBuilder or StringBuffer object
    • return the object as string

    Complexity Analysis

    • Time complexity : $$O(n)$$.

    • Space complexity : $$O(n))$$.


    Approach #2 Two Pointer Swap Method

    Intuition

    If you give a close look, reverse of a string is swapped characters which are at same distance from the extremes i.e 1st character swapped by the last, 2nd character swapped by the 2nd last.

    Algorithm

    • Initialize two pointers start and end, pointing to the first and last character respectively
    • loop until start < end
      • swap character at start with character at end
      • increment start and decrement end
    • return as string

    Java

    class Solution {
        public String reverseString(String s) {
            char ch[] = s.toCharArray();
            char temp = '\u0000';
            for(int start = 0, end = ch.length-1; start<end; start++,end--){
                temp = ch[start];
                ch[start] = ch[end];
                ch[end] = temp;
            }
            return new String(ch);
        }
    }
    

    Complexity Analysis

    • Time complexity : $$O(n) . n is half the number of characters in the string.

    • Space complexity : $$O(1)$$.

    Only downfall with the above approach is it is In-Place, you can use auxiliary space to store the result but this will lead Space Complexity to O(n).

    Thank You. Happy Coding :-)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.