LeetCode - #68 文本左右对齐

前言

我们社区陆续会将顾毅（Netflix 增长黑客，《iOS 面试之道》作者，ACE 职业健身教练。）的 Swift 算法题题解整理为文字版以方便大家学习与阅读。

LeetCode 算法到目前我们已经更新了 67 期，我们会保持更新时间和进度（周一、周三、周五早上 9:00 发布），每期的内容不多，我们希望大家可以在上班路上阅读，长久积累会有很大提升。

不积跬步，无以至千里；不积小流，无以成江海，Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言，我们会尽力满足大家的需求。

难度水平：困难

1. 描述

给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。

你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。

要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。

文本的最后一行应为左对齐，且单词之间不插入额外的空格。

注意:

• 单词是指由非空格字符组成的字符序列。
• 每个单词的长度大于 0，小于等于 maxWidth。
• 输入单词数组 words 至少包含一个单词。

2. 示例

示例 1

输入: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
输出:
[
   "This    is    an",
   "example  of text",
   "justification.  "
]

示例 2

输入:words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
输出:
[
  "What   must   be",
  "acknowledgment  ",
  "shall be        "
]
解释: 注意最后一行的格式应为 "shall be    " 而不是 "shall     be",
     因为最后一行应为左对齐，而不是左右两端对齐。       
     第二行同样为左对齐，这是因为这行只包含一个单词。

示例 3

输入:words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"]，maxWidth = 20
输出:
[
  "Science  is  what we",
  "understand      well",
  "enough to explain to",
  "a  computer.  Art is",
  "everything  else  we",
  "do                  "
]

约束条件：

• 1 <= words.length <= 300
• 1 <= words[i].length <= 20
• words[i] 由小写英文字母和符号组成
• 1 <= maxWidth <= 100
• words[i].length <= maxWidth

3. 答案

class TextJustification {
    func fullJustify(_ words: [String], _ maxWidth: Int) -> [String] {
        var res = [String]()
        var last = 0, currentLineLength = 0
        
        for (i, word) in words.enumerated() {
            if currentLineLength + word.count + (i - last) > maxWidth {
                
                res.append(buildLine(words, last, i - 1, maxWidth, currentLineLength))
                
                last = i
                currentLineLength = 0   
            }
            
            currentLineLength += word.count
        }
        
        res.append(buildLastLine(words, last, words.count - 1, maxWidth))
        
        return res
    }
    
    fileprivate func buildLine(_ words: [String], _ start: Int, _ end: Int, _ maxWidth: Int, _ currentLineLength: Int) -> String {
        var line = ""
        var extraSpaceNum = 0, spaceNum = 0
        
        if end > start {
            extraSpaceNum = (maxWidth - currentLineLength) % (end - start)
            spaceNum = (maxWidth - currentLineLength) / (end - start)
        } else {
            spaceNum = maxWidth - currentLineLength
        }
        
        for i in start...end {
            line.append(words[i])
            
            if start != end && i == end {
                break
            } 
            
            for _ in 0..<spaceNum {
                line.append(" ")
            }
            
            if extraSpaceNum > 0 {
                line.append(" ")
                extraSpaceNum -= 1
            }
        }
        
        return line
    }
    
    fileprivate func buildLastLine(_ words: [String], _ start: Int, _ end: Int, _ maxWidth: Int) -> String {
        var line = ""
        
        for i in start...end {
            line.append(words[i])
            
            if i < end {
                line.append(" ")
            }
        }
        
        while line.count < maxWidth {
            line.append(" ")
        }
        
        return line
    }
}

• 主要思想：对单词进行迭代，跟踪第一个单词的索引和该行的长度。插入带有固定空格和额外空格的空格。。
• 时间复杂度： O(n)
• 空间复杂度： O(n)

该算法题解的仓库：LeetCode-Swift

点击前往 LeetCode 练习

关于我们

我们是由 Swift 爱好者共同维护，我们会分享以 Swift 实战、SwiftUI、Swift 基础为核心的技术内容，也整理收集优秀的学习资料。

后续还会翻译大量资料到我们公众号，有感兴趣的朋友，可以加入我们。