ac solution code


  • 0
    /*
         Solution1. time = O(n); space = O(1)
         - Length of each line is `maxWidth`, fill gaps between words with whitespaces evenly.
              
         For each line, I first figure out which words can fit in. According to the code, these words are words[i] through words[i+k-1]. Then spaces are added between the words.
         The trick here is to use mod operation to manage the spaces that can't be evenly distrubuted: the first (L-l) % (k-1) gaps acquire an additional space.
         */
        func fullJustify(_ words: [String], _ maxWidth: Int) -> [String] {
            var lines = [String]()                              // Result: Lines array
            var lineStart = 0                                   // Current lineStart of words
            while lineStart < words.count {
                var chsLen = words[lineStart].characters.count  // Length of chars of current line words
                var lineEnd = lineStart + 1                     // lineEnd word lineStart(lineEnd+1) can fill in curLine
                while lineEnd < words.count &&                  // One line: fill in as many words if all chars len <= `maxWidth`
                      chsLen + 1 + words[lineEnd].characters.count <= maxWidth {// Length of curLine <= maxWidth
                    chsLen += 1 + words[lineEnd].characters.count// Update `chsLen` <-- "+1": prefix whitespace of curWord
                    lineEnd += 1                                 // lineEnd index + 1
                }
                lineEnd -= 1 //<--
                
                var line = ""
                var gaps = lineEnd - lineStart              // Words gaps count of current line
                if lineEnd == words.count - 1 || gaps == 0 {        // if lineEnd word or one word, left-justified: append whiteSpaces
                    for i in lineStart...lineEnd {
                        line += words[i] + " "                  // Insert one " " between words
                    }
                    if !line.isEmpty {                          // remove last " "
                        line.remove(at: line.index(before: line.endIndex))// remove lastCharacter: endIndex is lastPos + 1
                    }
                    for i in line.characters.count..<maxWidth {
                        line += " "                             // Fill remaining right part with whitespaces
                    }
                } else {// Else: more than one word - distribute whiteSpaces evenly between words
                    let avgSpaces = (maxWidth - chsLen) / gaps  // whilepsaces for each gap
                    let remainder = (maxWidth - chsLen) % gaps  // Remaining whitespaces: Can't be distributed evently (should be put to left greedyly)
                    for i in lineStart...lineEnd {              // Append words to curLine
                        line += words[i]
                        if i < lineEnd {                    // Fill in whitespaces between words, except last word of curLine
                            let adjustOne = (i - lineStart) < remainder ? 1 : 0
                            // Fill in avgSpaces first, and fill in one more whitespace before use up `remainder` whitespaces
                            for _ in 0..<(1 + avgSpaces + adjustOne) {// <-- +1: fixed 1 whitespace between words, already being counted in chsLen
                                line += " "
                            }
                        }
                    }
                }
                lines.append(line)                              // Append one line to result
                lineStart = lineEnd + 1                             // Update `lineStart` with `lineEnd`(lastIndexOfCurLine + 1), and move on to next line
            }
            return lines
        }
    

Log in to reply
 

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