题目描述
给定一个单词数组 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 <= 3001 <= words[i].length <= 20words[i] 由小写英文字母和符号组成1 <= maxWidth <= 100words[i].length <= maxWidth
解法
方法一：模拟
根据题意模拟即可，注意，如果是最后一行，或者这一行只有一个单词，那么要左对齐，否则要均匀分配空格。
时间复杂度 $O(L)$，空间复杂度 $O(L)$。其中 $L$ 为所有单词的长度之和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 | 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 | 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 | 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 | 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
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 | 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;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 | 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;
}
}
|