Two Pointers: Reverse Words in a String

by Raul Bojalil

HTML

<p>
Given a sentence, reverse the order of its words without affecting the order of letters within a given word.
</p>

<div class="markdownViewer select-text  markdown-default markdown-table markdown-viewer markdown-viewer-heading" role="none"><h2 class="hover-anchor" id="Solution" data-id="4054af96e33a26fd18f747c3a524038a">Solution<a href="#Solution"><span class="anchor-link">#</span></a></h2>
<p data-id="7218ad063784a539b14e59fa76a3a13e">In this problem, we first reverse the complete string. Now take two pointers, <code>start</code> and <code>end</code>, initialized with the start of the list, which is index <code>0</code>.</p>
<p data-id="3df82df2ee4c527e5d4009d6579149a5">Now, iterate a loop until <code>start</code> is less than the length of the list, and in each iteration, move the <code>end</code> pointer forward until it hits a space. At this point, we have a complete word starting from the <code>start</code> index to the <code>end-1</code> index, but with the characters in reverse order.</p>
<p data-id="e0cb3ce87ff965dfd1f0b85f2101764b">To change the order of characters, we call the <code>strRev</code> function with the starting and ending positions of the word. This will reverse the characters in the word.</p>
<p data-id="0b7782b9f92cb10cb28a6e6afd542da7">Now, we update the <code>start</code> and <code>end</code> pointers to the next of <code>end</code> pointer, which is basically the first character of the next word. Now, repeat this process for the next word. At the end of all iterations, we get the reversed words in the string.</p>
<p data-id="7042ae3734100c219f6f8108ac409d9a">The following illustration shows these steps in detail:</p>
</div>

JavaScript

function reverseWords(sentence) {
    // remove leading, trailing and multiple spaces
    sentence = sentence.trim().replace(/  +/g, ' ');
    // We need to convert the input strings
    // to lists of characters as strings are immutable in JavaScript
    sentence = [...sentence];
    let strLen = sentence.length;

    // We will first reverse the entire string.
    sentence = strRev(sentence, 0, strLen - 1);

    //  Now all the words are in the desired location, but
    //  in reverse order: "Hello World" -> "dlroW olleH".
    let start = 0,
        end = 0;

    // Now, let's iterate the reversed string and reverse each word in place.
    // "dlroW olleH" -> "World Hello"
    while (start < strLen) {

        // Find the end index of the word. 
        while (end < strLen && sentence[end] != " ")
            end += 1;

        // let's call our helper function to reverse the word in-place.
        strRev(sentence, start, end - 1);
        start = end + 1;
        end += 1;
    }
    return sentence.join("");
}

// a function that reverses a whole sentence character by character
function strRev(str, startRev, endRev) {
    // Starting from the two ends of the list, and moving
    // in towards the centre of the string, swap the characters
    while (startRev < endRev) {
        let temp = str[startRev]; // temp store for swapping
        str[startRev] = str[endRev]; // swap step 1
        str[endRev] = temp; // swap step 2

        startRev += 1; // move forwards towards the middle
        endRev -= 1; // move backwards towards the middle
    }
    return str;
}

    stringToReverse = [
        " Hello World ",
        "We love JavaScript",
        "The quick brown fox jumped over the lazy dog",
        "Hey",
        "To be or not to be",
        "AAAAA",
        " Hello     World "
    ];

    for (let i = 0; i < stringToReverse.length; i++) {
        console.log(
            i + 1 + ".\t Actual string:\t\t",
            stringToReverse[i]
        );
       ...