Javascript Reverse Words O(n) time O(1) space

How to Reverse Words in Javascript with O(n) Time and O(1) Space Complexity?#

Reversing words in a string is a common problem in programming. There are many ways to solve this problem, but we will focus on the O(n) time and O(1) space complexity approach using Javascript.

The Algorithm#

The algorithm we will use is simple. We will start by reversing the entire string, and then we will reverse each word in the string. To do this, we will use two pointers, one at the beginning of the word and one at the end of the word. We will swap the characters at the two pointers until they meet in the middle of the word.

The Code#

Here is the Javascript code that implements this algorithm:

function reverseWords(str) {
  let reversed = reverseString(str);
  let start = 0;
  let end = 0;
  while (end < reversed.length) {
    if (reversed[end] === ' ') {
      reversed = reverseWord(reversed, start, end - 1);
      start = end + 1;
    }
    end++;
  }
  reversed = reverseWord(reversed, start, end - 1);
  return reversed;
}

function reverseString(str) {
  return str.split('').reverse().join('');
}

function reverseWord(str, start, end) {
  let arr = str.split('');
  while (start < end) {
    let temp = arr[start];
    arr[start] = arr[end];
    arr[end] = temp;
    start++;
    end--;
  }
  return arr.join('');
}

The reverseWords() function takes a string as input and returns the reversed string with reversed words. It calls the reverseString() function to reverse the entire string and then uses two pointers to reverse each word.

The reverseString() function uses the split(), reverse(), and join() methods to reverse the entire string in one line of code.

The reverseWord() function takes a string, a start index, and an end index as input and returns the reversed word. It uses two pointers to swap the characters at the start and end indices until they meet in the middle of the word.

Example#

Let's test the function with an example:

let str = 'hello world';
console.log(reverseWords(str));
// Output: 'dlrow olleh'

The function correctly reverses the words in the string while maintaining the order of the words.