Day 6. Reverse String problems (two pointers)

• We cannot directly swap characters and change in-place with Javascript string, just like we did for array of characters.

  • why? Because String is immutable

• We cannot directly assign a letter via index to an empty string. you need to use + operation to write on the string.

First Attempt Code

// string => array => swap => string
var reverseWords = function(s) {
    let words = s.split(" ");
    for(let i = 0; i < words.length; i++) {
        words[i] = swap(words[i]);
    }
    return words.join(" ");
};

var swap = function(word) {
    let chars = word.split('');
    let leftP = 0;
    let rightP = chars.length - 1;
    while(leftP < rightP) {
        if(chars[leftP] !== chars[rightP]) {
            let leftChar = chars[leftP];
            chars[leftP] = chars[rightP];
            chars[rightP] = leftChar;
        }
        rightP--;
        leftP++;
    }
    return chars.join('');
}

Improved version

/**
 * @param {string} s
 * @return {string}
 */

// improved version of swap function above
function reverseString(s){
    let arr = s.split('');
    let length = ~~(arr.length/2);
    for(let i = 0; i< length; i++){
        [arr[i],arr[s.length-1-i]] = [arr[arr.length-1-i],arr[i]];
    }
    return arr.join('');
}
var reverseWords = function(s) {
    let arr = s.split(' ');
    for(let i = 0; i<arr.length; i++){
        arr[i] = reverseString(arr[i]);
    }
    return arr.join(' ')
};

Second Way

• I was trying to think of a way to stick with two pointers, but at the end, it doesn't seem to different.
• This is not too different from the first way, except that here I didn't separate the works. From clean code perspective, it would be better to take out content of while loop as separate function outside.
• Maybe in javascript, first way could be better or similar to this second method.

var reverseWords = function(s) {
    let wordStart = 0; 
    let wordEnd = 1;
    let newWords = [];

    while(wordEnd <= s.length) {

        // hits the space or end
        if(wordEnd === s.length || s[wordEnd] == ' ') {
          // extract word and reverse
          let word = s.substring(wordStart, wordEnd);
          let reverseWord = "";
          // add char from the end of substring
          for(let i = word.length - 1; i >= 0; i-- ) {
            reverseWord += word[i];
          }
          newWords.push(reverseWord);
          // update wordStart to a beginning of next word
          wordStart = wordEnd + 1;
        }
        // increment wordEnd index until it hits the space or end
        wordEnd++;
    }
    // console.log(newWords);
    return newWords.join(" ");
};

Python solution

• just interesting

class Solution:
    def reverseWords(self, s: str) -> str:
        return " ".join([word[::-1] for word in s.split()])

~~ operator

In JavaScript, ~~ is a bitwise operator that performs a double bitwise NOT operation.

The double bitwise NOT operator converts its operand to a signed 32-bit integer. It is equivalent to Math.floor() for non-negative numbers and Math.ceil() for negative numbers.

For example, ~~3.14 returns 3, and ~~(-3.14) returns -3.

The ~~ operator can be used as a faster alternative to Math.floor() or parseInt() in certain situations where you only need to convert a positive number to an integer. However, it should be used with caution as it can produce unexpected results for negative numbers or non-numeric inputs.

Relevant problem set

541. Reverse String II

---

Previous Challenge 344. Reverse String

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.

Relevant problem sets
More challenges
345. Reverse Vowels of a String
541. Reverse String II