Reverse a string in JavaScript without using an array-CodePudding

A simple way of reversing a string is as below:

const test = 'hello';

let i = 0;
let j = test.length - 1;

while (i < j) {
    let temp = test[i];
    test[j] = test[i];
    test[i] = temp;
    i  ;
    j--;
}
console.log(test);

If we try to access string using an index it works fine. For example console.log(test[2]) returns 'l'

But reversing a string using the method above returns unchanged string 'hello'. We need to use an array, reverse it and then join it to return the reversed string. But in that case we will be using an extra space. Can we do it without using an extra space?

CodePudding user response：

Strings are immutable in JavaScript. Therefore, they cannot be changed in-place. Any new string requires a new memory allocation, even when doing something as simple as

const str1 = "hello";
const str2 = str[0];

Leaves two strings in memory: "hello" and "h".

Since any attempt to produce a string will create at least one new string, it is therefore impossible to reverse a string without allocating space for a new string where the characters are reversed.

The minimum space complexity for this task is thusO(n) - scales linearly with the string length. Creating an array which can be rearranged in-place and then combined back to the reversed string fulfils this.

CodePudding user response：

Here is a recursive way of doing it:

const rev = s => s.length>1 ? s.at(-1) rev(s.slice(0,-1)) : s;

console.log(rev("This is a test string."))

CodePudding user response：

The final line of your question means that the answer is "no". We cannot do this without using extra space [in userland JS].

We could, however, do this if we relied on a function written in a systems programming language. And this is the C code used by V8 for Array#join. In such a language the binary representation of the reversed string could be constructed step by step and simply cast to be a UTF-16 string in the final step. I presume this approximates what Array#join does under the hood.

If your requirement is simply to avoid using an array, the following simply successively pulls the code units from the end of the input string and builds a new string from them.

This will fail horribly with surrogate pairs (eg emoji) and grapheme clusters.

const reverse = (s) => {
  let result = ''
  for(let x = s.length-1; x >= 0; x--) {
    result  = s[x]
  }
  return result
}

console.log(reverse('hello'))

CodePudding user response：

What about a hacky for loop?

const rev = (str) => {
  for(var i = str.length - 1; i >= 0; i--) {
    str  = str[i];
  }
  return str.slice(str.length / 2, str.length);
}

console.log(rev("t"));
console.log(rev("te"));
console.log(rev("tes"));
console.log(rev("test"));

CodePudding user response：

OP

"Can we do it without using an extra space."

nope.

Anyhow ... the OP's while based approached which this time does not try to change characters in place but programmatically a) removes character by character from the input value while b) concatenating the reversed result string ...

function reverseStringWithoutHelpOfArray(value) {
  value = String(value);                          // let i = 0;
  let result = '';                                // let j = test.length - 1;
                                                  // while (i < j) {
  while (value) {                                 //   let temp = test[i];
    result = result   value.slice(-1);            //   test[j] = test[i]; 
    value = value.substring(0, value.length - 1); //   test[i] = temp;
  }                                               //   i  ; j--;
  return result;                                  // }
}

console.log(
  reverseStringWithoutHelpOfArray('hallo')
);