Solution by ananai


  • 0

    Approach #1 std::reverse [Accepted]

    Algorithm

    Apply std::reverse on a string.

    string reverseString(string s) {
    
        reverse(s.begin(), s.end());
    
        return s;
    }
    

    Complexity Analysis

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

    reverse function works in linear time.

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

    Approach #2 Iterative [Accepted]

    Algorithm

    Iterate through a half of the string each time swap mirror elements, i.e. first and last elements etc.

    leetcode
    *      *
    eeetcodl
     *    *
    edetcoel
      *  *
    edotceel
       **
    edocteel
    
    string reverseString(string s) {
    
        for(int i = 0; i<s.length()/2; i++) {
            swap(s[i], s[s.length()-1-i]);
        }
    
        return s;
    }
    

    Complexity Analysis

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

    Every swap during iteration takes $$O(1)$$ time, total $$O(n)$$.

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

    Approach #3 Recursive Divide and Conquer [Accepted]

    Algorithm

    Keep dividing the string into halves and concatenate swapped halves.

    reverseString("et") + reverseString("le")
    (reverseString("t") + reverseString("e")) + (reverseString("l") + reverseString("e"))
    (("t") + ("e")) + (("e") + ("l"))
    
    string reverseString(string s) {
    
        int l = s.length();
    
        if (l<2) {
            return s;
        }
    
        return reverseString(s.substr(l/2)) + reverseString(s.substr(0, l/2));
    }
    

    Complexity Analysis

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

    Concatenation each time takes $$O(1)$$ making overall $$O(n)$$ time.

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

    Approach #4 Recursive Naive [Memory Limit Exceeded]

    Algorithm

    Get first character of the string and put it to the end. Call recursion of remaining substring.

    reverseString("code")
    (reverseString("ode")) + "c"
    ((reverseString("de")) + "o") + "c"
    (((reverseString("e") + "d") + "o") + "c"
    ((("e") + "d") + "o") + "c"
    
    string reverseString(string s) {
    
        if(s.length() == 0) {
            return s;
        }
    
        return reverseString(s.substr(1)) + s[0];
    }
    

    Complexity Analysis

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

    Concatenation each time consume $$O(1)$$ making overall $$O(n)$$ time.

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

Log in to reply
 

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