LeetCode 68. Text Justification 文本左右对齐算法分析及实现代码

发表于2019年1月30日由admin

原题目（中文翻译在后）：

Given an array of words and a width maxWidth, format the text such that each line has exactly maxWidth 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 maxWidth 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.

Note:

  • A word is defined as a character sequence consisting of non-space characters only.
  • Each word’s length is guaranteed to be greater than 0 and not exceed maxWidth.
  • The input array words contains at least one word.

Example 1:

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

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

Example 2:

Input: words = ["What","must","be","acknowledgment","shall","be"] maxWidth = 16 
Output: 
[   "What   must   be",
    "acknowledgment  ",
    "shall be        " ] 

Explanation: Note that the last line is "shall be    " instead of "shall     be", because the last line must be left-justified instead of fully-justified. Note that the second line is also left-justified becase it contains only one word.

Example 3:

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

Output: 
[   "Science  is  what we",
    "understand      well",
    "enough to explain to",
    "a  computer.  Art is",
    "everything  else  we",
    "do                  " ]

题目中文翻译：

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

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

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

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

说明:

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

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=68

题目分析：

虽然这道题在LeetCode总难易榜上排名第七，但解题难度并不是很大。关键注意以下几点，便可成功过关。

  1. 每一行每个单词间至少要有一个空格，但最后一个单词末尾应没有空格（下述2和3的情况除外）。
  2. 末尾行所有单词左对齐。也就是说除了单词间的一个空格之外，其余空格应加到末尾。
  3. 非末尾行只有一个单词时，按末尾行处理。

注意了以上几点之后，题目中提到要使用贪心算法，也就是说，每一行要尽可能显示更多的单词，具体实现步骤参照代码中的注释即可。

实现代码：

 
final String space = " "; // 定义一个空格
public List fullJustify(String[] words, int maxWidth) {
     // 返回结果List
     List result = new ArrayList<>();
     // 当前行已使用长度
     int currentLength = 0;
     // 当前行已存入的单词
     List oneLine = new ArrayList<>();
     for (int i = 0; i < words.length; i++) {
         String word = words[i];
         int length = word.length();
         // 如果当前行还能放下当前单词
         if (maxWidth - currentLength - length >= 0) {
             currentLength += length;
             // 因为除了末尾单词外每个单词后需加空格，在此判读
             // 如果还有富余添加空格，则添加
             // 如果此行已满，说明这是当前行最后的单词，则无需添加
             if (maxWidth - currentLength > 0) {
                 currentLength++;
                 oneLine.add(word + space);
             } else {
                 oneLine.add(word);
             }
             // 如果当前单词是数组中最后一个单词，
             // 执行拼接当前行所有单词操作，getLine()方法
             if (i == words.length - 1) {
                 int rest = maxWidth - currentLength;
                 String thisLine = getLine(oneLine, rest, true);
                 result.add(thisLine);
                 oneLine.clear();
                 currentLength = 0;
             }
         } else {
             // 当前行已经不能放下当前单词，当前行结束
             // 执行拼接当前行所有单词操作，getLine()方法
             int rest = maxWidth - currentLength;
             String thisLine = getLine(oneLine, rest, false);
             result.add(thisLine);
             // 当前行结束时，应清空oneLine列表
             oneLine.clear();
             // 当前行结束时，同样currentLength归零
             currentLength = 0;
             // 注意当前单词并没有添加到当前行中，
             // 所以i应减一，把当前单词放入下一行首位处理
             i--;
         }
     }
     return result;
 }
// oneLine 当前行所有单词列表
// rest 所有单词长度总和与行宽maxWidth的差
// isLastline 是否为末尾行
private String getLine(List oneLine, int rest, boolean isLastline) {
     // 如果是末尾行或者该行只有一个单词时，将所有剩余空格加到末尾
     if (isLastline || oneLine.size() == 1) {
         while (rest > 0) {
             oneLine.set(oneLine.size() - 1, oneLine.get(oneLine.size() - 1) + space);
             rest--;
         }
     }
         // 非末尾行或者该行单词数大于等于2时
         else {
         // 因为末尾单词可能会存在末尾空格，此处应该删除掉
         // 同时注意rest应该加一
         if (oneLine.get(oneLine.size() - 1).endsWith(space)) {
             oneLine.set(oneLine.size() - 1, oneLine.get(oneLine.size() - 1).trim());
             rest++;
         }
         // 将剩余空格平均添加到除最后一个单词之外的每个单词后
         int index = 0;
         while (rest > 0) {
             oneLine.set(index, oneLine.get(index) + space);
             // 循环至倒数第二个单词后，将坐标index返回0继续
             if (index == oneLine.size() - 2) {
                 index = 0;
             } else {
                 index++;
             }
             // 减去消耗掉的空格数，直到rest为0为止
             rest--;
         }
     }
     // 将当前行所有单词拼接成一个字符串 
     StringBuilder sb = new StringBuilder(); 
     for (String line : oneLine) { 
         sb.append(line); 
     } 
     return sb.toString();
 }

本解用时1ms，虽然不是最优解，但理解上应该比较简单。

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-68-text-justification-文本左右对齐算法分析及实现代码/
此条目发表在leetcode分类目录，贴了, , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。