JavaScript O(1) space on character array


  • 0
    T

    Inspired by other O(1) space solutions. As others have mentioned, Strings are immutable in JS, so we have to split the input into an Array of 1 character Strings to do in-place modifications.

    /**
     * Operates on an array of characters in O(N) time, O(1) space.
     * @param {string} str
     * @returns {string}
     */
    function reverseWords(str) {
        // This part is not O(1) space, but it's just our integration code with LeetCode.
        // Outside this sandbox, we'd ask callers to pass an a character Array instead of a String
        // for best performance.
        return _reverseWords(str.split('')).join('');
    }
    
    function _reverseWords(chars) {
        // Reverse the whole string
        reverse(chars);
    
        let spaceCount = 0;
        let wordCount = 0;
        for(let i=0; i<chars.length; i++) {
            // Consume spaces
            if(chars[i] === ' ') {
                spaceCount++;
                continue;
            }
    
            // Re-reverse a word
            let j; // word end index
            for(j=i; j<chars.length && chars[j] !== ' '; j++) {}
            j -= 1;
            reverse(chars, i, j);
            wordCount += 1;
    
            // Shift the word left to collapse extra space
            shiftLeft(chars, i, j, spaceCount - wordCount + 1);
    
            // Advance through the word
            i=j;
        }
    
        // Remove trailing space
        while(spaceCount > wordCount - 1) {
          spaceCount--;
          chars.pop();
        }
    
        return chars;
    }
    
    // In place reverse, both indicies inclusive
    function reverse(chars, lo, hi) {
        lo = lo || 0;
        if(typeof hi === 'undefined') hi = chars.length - 1;
        while(lo < hi){
            tmp = chars[lo];
            chars[lo] = chars[hi];
            chars[hi] = tmp;
            lo++; hi--;
        }
    }
    
    // In place shift, both indicies inclusive
    function shiftLeft(chars, start, end, offset) {
        for(let k=start-offset; k<=end-offset; k++) {
            chars[k] = chars[k+offset];
        }
        // Add a trailing space
        if(offset) {
          chars[end - offset + 1] = ' ';
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.