Question

68. 文本左右对齐

English Version

题目描述

给定一个单词数组 words 和一个长度 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        "
]
解释: 注意最后一行的格式应为 "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

解法

方法一：模拟

根据题意模拟即可，注意，如果是最后一行，或者这一行只有一个单词，那么要左对齐，否则要均匀分配空格。

时间复杂度 $O(L)$，空间复杂度 $O(L)$。其中 $L$ 为所有单词的长度之和。

class Solution:
  def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
    ans = []
    i, n = 0, len(words)
    while i < n:
      t = []
      cnt = len(words[i])
      t.append(words[i])
      i += 1
      while i < n and cnt + 1 + len(words[i]) <= maxWidth:
        cnt += 1 + len(words[i])
        t.append(words[i])
        i += 1
      if i == n or len(t) == 1:
        left = ' '.join(t)
        right = ' ' * (maxWidth - len(left))
        ans.append(left + right)
        continue
      space_width = maxWidth - (cnt - len(t) + 1)
      w, m = divmod(space_width, len(t) - 1)
      row = []
      for j, s in enumerate(t[:-1]):
        row.append(s)
        row.append(' ' * (w + (1 if j < m else 0)))
      row.append(t[-1])
      ans.append(''.join(row))
    return ans

class Solution {
  public List<String> fullJustify(String[] words, int maxWidth) {
    List<String> ans = new ArrayList<>();
    for (int i = 0, n = words.length; i < n;) {
      List<String> t = new ArrayList<>();
      t.add(words[i]);
      int cnt = words[i].length();
      ++i;
      while (i < n && cnt + 1 + words[i].length() <= maxWidth) {
        cnt += 1 + words[i].length();
        t.add(words[i++]);
      }
      if (i == n || t.size() == 1) {
        String left = String.join(" ", t);
        String right = " ".repeat(maxWidth - left.length());
        ans.add(left + right);
        continue;
      }
      int spaceWidth = maxWidth - (cnt - t.size() + 1);
      int w = spaceWidth / (t.size() - 1);
      int m = spaceWidth % (t.size() - 1);
      StringBuilder row = new StringBuilder();
      for (int j = 0; j < t.size() - 1; ++j) {
        row.append(t.get(j));
        row.append(" ".repeat(w + (j < m ? 1 : 0)));
      }
      row.append(t.get(t.size() - 1));
      ans.add(row.toString());
    }
    return ans;
  }
}

class Solution {
public:
  vector<string> fullJustify(vector<string>& words, int maxWidth) {
    vector<string> ans;
    for (int i = 0, n = words.size(); i < n;) {
      vector<string> t = {words[i]};
      int cnt = words[i].size();
      ++i;
      while (i < n && cnt + 1 + words[i].size() <= maxWidth) {
        cnt += 1 + words[i].size();
        t.emplace_back(words[i++]);
      }
      if (i == n || t.size() == 1) {
        string left = t[0];
        for (int j = 1; j < t.size(); ++j) {
          left += " " + t[j];
        }
        string right = string(maxWidth - left.size(), ' ');
        ans.emplace_back(left + right);
        continue;
      }
      int spaceWidth = maxWidth - (cnt - t.size() + 1);
      int w = spaceWidth / (t.size() - 1);
      int m = spaceWidth % (t.size() - 1);
      string row;
      for (int j = 0; j < t.size() - 1; ++j) {
        row += t[j] + string(w + (j < m ? 1 : 0), ' ');
      }
      row += t.back();
      ans.emplace_back(row);
    }
    return ans;
  }
};

func fullJustify(words []string, maxWidth int) (ans []string) {
  for i, n := 0, len(words); i < n; {
    t := []string{words[i]}
    cnt := len(words[i])
    i++
    for i < n && cnt+1+len(words[i]) <= maxWidth {
      cnt += 1 + len(words[i])
      t = append(t, words[i])
      i++
    }
    if i == n || len(t) == 1 {
      left := strings.Join(t, " ")
      right := strings.Repeat(" ", maxWidth-len(left))
      ans = append(ans, left+right)
      continue
    }
    spaceWidth := maxWidth - (cnt - len(t) + 1)
    w := spaceWidth / (len(t) - 1)
    m := spaceWidth % (len(t) - 1)
    row := strings.Builder{}
    for j, s := range t[:len(t)-1] {
      row.WriteString(s)
      row.WriteString(strings.Repeat(" ", w))
      if j < m {
        row.WriteString(" ")
      }
    }
    row.WriteString(t[len(t)-1])
    ans = append(ans, row.String())
  }
  return
}

function fullJustify(words: string[], maxWidth: number): string[] {
  const ans: string[] = [];
  for (let i = 0, n = words.length; i < n; ) {
    const t: string[] = [words[i]];
    let cnt = words[i++].length;
    while (i < n && cnt + 1 + words[i].length <= maxWidth) {
      t.push(words[i]);
      cnt += 1 + words[i++].length;
    }
    if (i === n || t.length === 1) {
      const left: string = t.join(' ');
      const right: string = ' '.repeat(maxWidth - left.length);
      ans.push(left + right);
      continue;
    }
    const spaceWidth: number = maxWidth - (cnt - t.length + 1);
    const w: number = Math.floor(spaceWidth / (t.length - 1));
    const m: number = spaceWidth % (t.length - 1);
    const row: string[] = [];
    for (let j = 0; j < t.length - 1; ++j) {
      row.push(t[j]);
      row.push(' '.repeat(w + (j < m ? 1 : 0)));
    }
    row.push(t[t.length - 1]);
    ans.push(row.join(''));
  }
  return ans;
}

public class Solution {
  public IList<string> FullJustify(string[] words, int maxWidth) {
    var ans = new List<string>();
    for (int i = 0, n = words.Length; i < n;) {
      var t = new List<string>();
      t.Add(words[i]);
      int cnt = words[i].Length;
      ++i;
      while (i < n && cnt + 1 + words[i].Length <= maxWidth) {
        t.Add(words[i]);
        cnt += 1 + words[i].Length;
        ++i;
      }
      if (i == n || t.Count == 1) {
        string left = string.Join(" ", t);
        string right = new string(' ', maxWidth - left.Length);
        ans.Add(left + right);
        continue;
      }
      int spaceWidth = maxWidth - (cnt - t.Count + 1);
      int w = spaceWidth / (t.Count - 1);
      int m = spaceWidth % (t.Count - 1);
      var row = new StringBuilder();
      for (int j = 0; j < t.Count - 1; ++j) {
        row.Append(t[j]);
        row.Append(new string(' ', w + (j < m ? 1 : 0)));
      }
      row.Append(t[t.Count - 1]);
      ans.Add(row.ToString());
    }
    return ans;
  }
}