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. class Solution {
  4. public:
  5.     vector<string> fullJustify(vector<string> &words, int L) {
  6.         vector<string> result;
  7.         const int n = words.size();
  8.         int begin = 0, len = 0; // 当前行的起点，当前长度
  9.         for (int i = 0; i < n; ++i) {
  10.             if (len + words[i].size() + (i - begin) > L) {
  11.                 result.push_back(connect(words, begin, i - 1, len, L, false));
  12.                 begin = i;
  13.                 len = 0;
  14.             }
  15.             len += words[i].size();
  16.         }
  17.         // 最后一行不足L
  18.         result.push_back(connect(words, begin, n - 1, len, L, true));
  19.         return result;
  20.     }
  21.     /**
  22.      * @brief 将 words[begin, end] 连成一行
  23.      * @param[in] words 单词列表
  24.      * @param[in] begin 开始
  25.      * @param[in] end 结束
  26.      * @param[in] len words[begin, end]所有单词加起来的长度
  27.      * @param[in] L 题目规定的一行长度
  28.      * @param[in] is_last 是否是最后一行
  29.      * @return 对齐后的当前行
  30.      */
  31.     string connect(vector<string> &words, int begin, int end,
  32.             int len, int L, bool is_last) {
  33.         string s;
  34.         int n = end - begin + 1;
  35.         for (int i = 0; i < n; ++i) {
  36.             s += words[begin + i];
  37.             addSpaces(s, i, n - 1, L - len, is_last);
  38.         }
  40.         if (s.size() < L) s.append(L - s.size(), ' ');
  41.         return s;
  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.     void addSpaces(string &s, int i, int n, int L, bool is_last) {
  54.         if (n < 1 || i > n - 1) return;
  55.         int spaces = is_last ? 1 : (L / n + (i < (L % n) ? 1 : 0));
  56.         s.append(spaces, ' ');
  57.     }
  58. };

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