#4 Leetcode 344 Reverse String

tags:Recursion Easy

Problem

Write a function that reverses a string. The input string is given as an array of characters s.
You must do this by modifying the input array in-place with O(1) extra memory.~

Example 1

Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

Example 2

Input: s = ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]

---

Solutions

Official

// _(┐ ◟;ﾟдﾟ)ノ

---

Everyone's

東

// Time O(n) | Space O(1); n is the input length
var reverseString = function(s) {
    let leftPointer = 0;
    let rightPointer = s.length - 1;
    
    while(leftPointer < rightPointer) {
        const oldLeft = s[leftPointer];
        const oldRight = s[rightPointer];
        s[leftPointer] = oldRight;
        s[rightPointer] = oldLeft;
        leftPointer ++;
        rightPointer --;
    }
    
    return s;
};

YC

/**
 * time: O(n) - where n is the length of the string
 * space: O(n) - where n is the length of the string
 */

var reverseString = function(s) {
    const reverse = (left, right) => {
        if(left > right) return s;
        [s[left], s[right]] = [s[right], s[left]]; 
        return reverse(left + 1, right - 1);
    }
    reverse(0, s.length - 1);
};

Hao

/**
 * Time complexity would be O(n) which n is arr.length - 1.
 * Space complexity would be O(n) which n is arr.length - 1.
 */

var reverseString = function(s) {
  const reverseStringInner = (arr, idx) => {
    const { length } = arr;
    const isOdd = length % 2 === 1;

    if (isOdd && idx === ((length - 1) / 2)) return arr;
    else if (idx === length / 2) return arr;

    const leftIdx = idx;
    const leftValue = arr[leftIdx];
    const rightIdx = (arr.length - 1) - idx;
    const rightValue = arr[rightIdx];
    arr[leftIdx] = rightValue;
    arr[rightIdx] = leftValue;

    return reverseStringInner(arr, idx + 1);
  };
  return reverseStringInner(s, 0);
};

月

// Time O(n) Space O(n)
var reverseString = function(s, index = 0) {
    const len = s.length, lastIndex = len - 1;
    [s[index], s[lastIndex - index]] = [s[lastIndex - index], s[index]];
    if(index + 1 < len / 2){
        return reverseString(s, index + 1);
    }
    return s
};

---

Supplement / Discussion

https://www.freecodecamp.org/news/how-recursion-works-explained-with-flowcharts-and-a-video-de61f40cb7f9/