LeetCode.文本左右对齐

给定一个单词数组和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。你应该使用“贪心算法”来放置给定的单词；也就是说，尽

可能多地往每行中放置单词。必要时可用空格 ‘ ‘ 填充，使得每行恰好有 maxWidth 个字符。要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。文本的最后一行应为左对齐，且单词之间不插入额外的空格。

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

• 示例 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 “
  ]
• 示例 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 “
  ]

解法：

``` scala
object FullJustify {

 def main(args: Array[String]): Unit = {
      println(
           fullJustify(
                Array("This", "is", "an", "example", "of", "text", "justification."),
                16
           )
      )

      println(
           fullJustify(
                Array("What", "must", "be", "acknowledgment", "shall", "be"),
                16
           )
      )

      println(
           fullJustify(
                Array("Science", "is", "what", "we", "understand", "well", "enough", "to", "explain", "to", "a",
                     "computer.", "Art", "is", "everything", "else", "we", "do"),
                20
           )
      )
 }

 def fullJustify(words: Array[String], maxWidth: Int): List[String] = {
      val res = new ListBuffer[String]()
      var curList = ListBuffer[String]()
      var curLen = 0
      var first = true
      words.foreach(a => {
           if (curLen + a.length + (if (first) 0 else 1) > maxWidth) {
                first = true
                res += parse(curList.toList, maxWidth, curLen)
                curLen = a.length
                curList.clear()
                curList += (a)
                first = false
           } else {
                curLen += (a.length + (if (first) 0 else 1))
                curList += (a)
                first = false
           }
      })

      res += curList.mkString(" ") + genKSpace(maxWidth - curList.mkString(" ").length)
      res.toList
 }

 def parse(strs: List[String], maxWidth: Int, len: Int): String = {
      val spaceNum = maxWidth - (len - (strs.length - 1))
      val bucketNum = strs.length - 1

      if (bucketNum == 0) {
           return strs(0) + genKSpace(spaceNum)
      }

      val avgNum = spaceNum / bucketNum
      val leftNum = spaceNum % bucketNum

      val space = new Array[String](bucketNum)
      for (i <- 0 until bucketNum) {
           if (i < leftNum) {
                space(i) = genKSpace(avgNum + 1)
           } else {
                space(i) = genKSpace(avgNum)
           }
      }

      var res = ""
      for (i <- 0 until strs.length) {
           res += strs(i) + (if (i < bucketNum) space(i) else "")
      }
      res
 }

 def genKSpace(k: Int): String = {
      var res = ""
      for (i <- 0 until k) {
           res += " "
      }
      res
 }

}
``` scala