Text Justification

描述

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly L characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left justified and no extra space is inserted between words.

For example,

words: ["This", "is", "an", "example", "of", "text", "justification."]

L: 16.

Return the formatted lines as:

  1. [
  2.    "This    is    an",
  3.    "example  of text",
  4.    "justification.  "
  5. ]

Note: Each word is guaranteed not to exceed L in length.

Corner Cases:

  • A line other than the last line might contain only one word. What should you do in this case?
  • In this case, that line should be left

    分析

无

代码

  1. // Text Justification
  2. // 时间复杂度O(n)，空间复杂度O(1)
  3. public class Solution {
  4.     public List fullJustify(String[] words, int maxWidth) {
  5.         List result = new ArrayList<>();
  6.         final int n = words.length;
  7.         int begin = 0, len = 0; // 当前行的起点，当前长度
  8.         for (int i = 0; i < n; ++i) {
  9.             if (len + words[i].length() + (i - begin) > maxWidth) {
  10.                 result.add(connect(words, begin, i - 1, len, maxWidth, false));
  11.                 begin = i;
  12.                 len = 0;
  13.             }
  14.             len += words[i].length();
  15.         }
  16.         // 最后一行不足 maxWidth
  17.         result.add(connect(words, begin, n - 1, len, maxWidth, true));
  18.         return result;
  19.     }
  20.     /**
  21.      * @brief 将 words[begin, end] 连成一行
  22.      * @param[in] words 单词列表
  23.      * @param[in] begin 开始
  24.      * @param[in] end 结束
  25.      * @param[in] len words[begin, end]所有单词加起来的长度
  26.      * @param[in] L 题目规定的一行长度
  27.      * @param[in] is_last 是否是最后一行
  28.      * @return 对齐后的当前行
  29.      */
  30.     private static String connect(String[] words, int begin, int end,
  31.                    int len, int L, boolean is_last) {
  32.         StringBuilder sb = new StringBuilder();
  33.         final int n = end - begin + 1;
  34.         for (int i = 0; i < n; ++i) {
  35.             sb.append(words[begin + i]);
  36.             addSpaces(sb, i, n - 1, L - len, is_last);
  37.         }
  39.         final int m = L - sb.length();
  40.         for (int i = 0; i < m; ++i) sb.append(' ');
  41.         return sb.toString();
  42.     }
  44.     /**
  45.      * @brief 添加空格.
  46.      * @param[inout]s 一行
  47.      * @param[in] i 当前空隙的序号
  48.      * @param[in] n 空隙总数
  49.      * @param[in] L 总共需要添加的空额数
  50.      * @param[in] is_last 是否是最后一行
  51.      * @return 无
  52.      */
  53.     private static void addSpaces(StringBuilder sb, int i,
  54.                                   int n, int L, boolean is_last) {
  55.         if (n < 1 || i > n - 1) return;
  56.         int spaces = is_last ? 1 : (L / n + (i < (L % n) ? 1 : 0));
  57.         for (int j = 0; j < spaces; ++j) sb.append(' ');
  58.     }
  59.  }

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/simulation/text-justification.html