JavaScript/ES6 Solution


  • 0
    U

    Understanding The Problem

    The problem looks easy to understand but it has a few corner cases that need to be kept in mind before successfully submitting it. Let's take a look at a few of those corner cases:

    1. What happens when words array has only one word and its length is less than or equal to L?
    2. What happens when words array has only one word and its length is greater than L?
    3. What happens when last line has multiple words?
    4. What happens when there's only one line and it has multiple words?

    Take a moment to guess those answers, then match your guesses with the answers below:

    1. Return the word.
    2. Return the word, pad extra spaces at the end.
    3. Multiple words should be separated by one space, with extra spaces trailed at the end.
    4. Treat it as the last line (as described in answer above).

    Outlining Solution

    At a very high level, solution can be outlined like this:

    1. Create word buckets. A bucket is an array of words which can fit in one line.
    2. Insert multiple spaces between words in buckets other than last bucket.
    3. Insert single spaces between words in last bucket. Insert extra spaces at the end.

    Solution

    Initial Function

    This is the function we need to implement with our solution.

    /**
     * @param {string[]} words
     * @param {number} maxWidth
     * @return {string[]}
     */
    var fullJustify = function(words, maxWidth) {
    };
    

    High Level Solution

    /**
     * @param {string[]} words
     * @param {number} maxWidth
     * @return {string[]}
     */
    var fullJustify = function(words, maxWidth) {
        // let's split one big input array into multiple sub-arrays
        const buckets = makeWordBuckets(words, maxWidth)
    
        // if this is last bucket, invoke padLastBucket
        // otherwise invoke padNonLastBucket
        const paddedBuckets = buckets.map((bucket, index) => index < (buckets.length - 1) ? padNonLastBucket(bucket, maxWidth) : padLastBucket(bucket, maxWidth))
    
        // join the words in buckets together to make text lines
        const paddedStrings = paddedBuckets.map(bucket => bucket.join(''))
        
        return paddedStrings
    };
    

    Notice that we have divided our bigger problem into multiple smaller problems. Completing our solution is a matter of solving those smaller problems by implementing following functions:

    1. makeWordBuckets()
    2. padNonLastBucket()
    3. padLastBucket()

    Implementing makeWordBuckets()

    const makeWordBuckets = (words, maxWidth) => {
        const output = []
        let index = 0
        
        while ( index < words.length ) {
            const bucket = []
            
            do {
                bucket.push(words[index])
                index++
            } while ( index < words.length && getBucketLengthWSpaces(bucket) <= maxWidth )
                
            if ( getBucketLengthWSpaces(bucket) > maxWidth ) {
                bucket.splice(bucket.length - 1, 1)
                index--
            }
            
            output.push(bucket)
        }
        
        return output
    }
    

    Implementing padNonLastBucket()

    Most of the logic in padNonLastBucket() and padLastBucket() is the same, so I've moved common logic into another function padBucket() which can be parameterized to output different results.

    const padMultiWordBucket = (bucket, maxWidth) => {
        const diff = maxWidth - getBucketLength(bucket)
        const spaceCount = bucket.length - 1
        const spaceWidth = Math.floor( diff / spaceCount )
        const spaceExtra = diff % spaceCount
        
        return padBucket(bucket, spaceWidth, spaceExtra, maxWidth)
    }
    

    Implementing padLastBucket()

    const padLastBucket = (bucket, maxWidth) => padBucket(bucket, 1, 0, maxWidth)
    

    Additional Utility Functions

    const makeSpaceString = count => Array.from(Array(count)).map(() => ' ').join('')
    const getBucketLength = bucket => bucket.reduce((sum, word) => sum + word.length, 0)
    const getBucketLengthWSpaces = bucket => getBucketLength(bucket) + bucket.length - 1
    const padBucket = (bucket, spaceWidth, spaceExtra, maxWidth) => {
        const output = bucket.reduce((paddedBucket, word, index) => index < (bucket.length - 1)
                      ? paddedBucket.concat([word, makeSpaceString(spaceWidth + (spaceExtra-- > 0 ? 1 : 0))])
                      : paddedBucket.concat([word]), [])
        
        const diff = maxWidth - getBucketLength( output )
        
        if ( diff > 0 ) {
            output.push(makeSpaceString(diff))   
        }
        
        return output
    }
    

    Conclusion

    Put all of those functions together and voila: there's your solution.

    A lot of people implement their solutions with one big function. Personally I find it very hard to keep all of that information in my head at the same time. I tend to think and solve problems layer by layer, hence dividing a bigger problem into smaller problems makes it easier for me to approach the problem. Hence you see multiple functions there.

    I'd love to heard your comments and feedback, so please share what you think.


Log in to reply
 

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