Short JavaScript O(n) solution


  • 1

    The two-pass version where we preprocess the words into rows is easier to understand:

    var fullJustify = function(words, maxWidth) {
        const res = [[]];
        res[0].letters = 0;
        for (let word of words) {
            let row = res[res.length - 1];
            if (row.length && row.letters + row.length + word.length > maxWidth) {
                res.push([]);
                row = res[res.length - 1];
                row.letters = 0;
            }
            row.push(word);
            row.letters += word.length;
        }
        for (let r = 0; r < res.length; r++) {
            let row = res[r];
            if (row.length === 1 || r === res.length - 1) {
                res[r] = row.join(' ') + ' '.repeat(maxWidth - row.letters - row.length + 1);
                continue;
            }
            let line = row[0];
            let spaces = maxWidth - row.letters;
            let minSpaces = ' '.repeat(Math.floor(spaces / (row.length - 1)));
            let addSpace = spaces % (row.length - 1);
            for (let w = 1; w < row.length; w++) {
                line += minSpaces + (w <= addSpace ? ' ' : '') + row[w];
            }
            res[r] = line;
        }
        return res;
    };
    

    We can also do this in one pass:

    var fullJustify = function(words, maxWidth) {
        for (let res = [[]], i = 0, letters = 0; i <= words.length; letters += words[i++].length) {
            let row = res[res.length - 1];
            if (i === words.length || row.length && letters + row.length + words[i].length > maxWidth) {
                if (row.length === 1 || i === words.length) {
                    res[res.length - 1] = row.join(' ') + ' '.repeat(maxWidth - letters - row.length + 1);
                    if (i === words.length) return res;
                } else {
                    let line = row[0];
                    let spaces = maxWidth - letters;
                    let minSpaces = ' '.repeat(Math.floor(spaces / (row.length - 1)));
                    let addSpace = spaces % (row.length - 1);
                    for (let w = 1; w < row.length; w++) {
                        line += minSpaces + (w <= addSpace ? ' ' : '') + row[w];
                    }
                    res[res.length - 1] = line;
                }
                res.push([]);
                letters = 0;
            }
            res[res.length - 1].push(words[i]);
        }
    };
    

    I prefer the longer version, as there isn't any speed/space advantage either way.


Log in to reply
 

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