68. Text Justification - cocoder39/coco39_LC GitHub Wiki

Notes 2020:

capabilities to demonstrate in interview:

  • able to break down the problem to subproblem
  • able to write clean and maintainable code
class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        def justify(wordsInLine, totalWordsLength, isLastLine=False):
            if len(wordsInLine) == 1 or isLastLine:
                return leftJustify(wordsInLine)
            return fullyJustify(wordsInLine, totalWordsLength)
            
        def leftJustify(wordsInLine):
            lineResult = [wordsInLine[0]]
            remainingSpaces = maxWidth - len(wordsInLine[0])
            for i in range(1, len(wordsInLine)):
                lineResult.append(' ')
                lineResult.append(wordsInLine[i])
                remainingSpaces -= 1 + len(wordsInLine[i])
            lineResult.append(' ' * remainingSpaces)
            return ''.join(lineResult)
            
        def fullyJustify(wordsInLine, totalWordsLength):
            lineResule = [wordsInLine[0]]
            totalSpaces = maxWidth - totalWordsLength
            count = len(wordsInLine)
            for i in range(1, count):
                spacesToInsert = math.ceil(totalSpaces / (count - i))
                totalSpaces -= spacesToInsert
                lineResule.append(' ' * spacesToInsert)
                lineResule.append(wordsInLine[i])
            return ''.join(lineResule)
                
        line = []
        wordsLen = 0
        res = []
        for i, word in enumerate(words):
            if wordsLen + len(line) + len(word) <= maxWidth:
                line.append(word)
                wordsLen += len(word)
            else:
                res.append(justify(line[:], wordsLen))
                line = [word]
                wordsLen = len(word)
        
        if line:
            res.append(justify(line[:], wordsLen, True))
        
        return res

============================================================

corner cases:

  • input: [""], 3
  • last line

two choices: append a word and corresponding spaces, finally append last word; or append one word first, then append spaces before appending the rest words. first choice makes code elegant.

time complexity is O(n)

vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> res;
        int start = 0;
        while (start < words.size()) {
            int wordsCnt = 0, wordsLength = 0;
            for (int len = 0, end = start; end < words.size() && len + words[end].length() <= maxWidth; end++) {
                len += words[end].length() + 1;
                wordsCnt++;
                wordsLength += words[end].length();
            }
            
            string line = words[start];
            for (int i = 0; i < wordsCnt - 1; i++) {
                if (start + wordsCnt == words.size()) { //last line
                    line.push_back(' ');
                } else {
                    int even = (maxWidth - wordsLength) / (wordsCnt - 1);
                    int uneven = i < (maxWidth - wordsLength) % (wordsCnt - 1) ? 1 : 0;
                    line += string(even + uneven, ' ');
                }
                line += words[start + 1 + i];
            }
            line += string(maxWidth - line.length(), ' ');
            res.push_back(line);
            start += wordsCnt;
        }
        return res;
    }
⚠️ **GitHub.com Fallback** ⚠️