难度中等
题目描述
给定一个由空格分隔的单词组成的字符串 sentence 和一个整数 k。你的任务是将 sentence 分成多行，每行中的字符数最多为 k。你可以假设 sentence 不以空格开头或结尾，并且 sentence 中的单词由单个空格分隔。
你可以通过在 sentence 中的单词间插入换行来分隔 sentence 。一个单词不能被分成两行。每个单词只能使用一次，并且单词顺序不能重排。同一行中的相邻单词应该由单个空格分隔，并且每行都不应该以空格开头或结尾。
一行长度为 n 的字符串的分隔成本是 (k - n)2 ，总成本就是除开最后一行以外的其它所有行的分隔成本之和。
- 以
sentence = "i love leetcode" 和k = 12为例： - 将
sentence 分成 "i", "love", 和"leetcode" 的成本为 (12 - 1)2 + (12 - 4)2 = 185。 - 将
sentence 分成 "i love", 和"leetcode" 的成本为 (12 - 6)2 = 36。 - 将
sentence 分成 "i", 和"love leetcode" 是不可能的，因为 "love leetcode" 的长度大于 k。
返回将sentence分隔成行的最低的可能总成本。
示例 1:
输入: sentence = "i love leetcode", k = 12
输出: 36
解释:
将 sentence 分成"i", "love", 和"leetcode" 的成本为 (12 - 1)2 + (12 - 4)2 = 185.
将 sentence 分成"i love", 和"leetcode" 的成本为 (12 - 6)2 = 36.
将 sentence 分成"i", "love leetcode" 是不可能的，因为 "love leetcode" 的长度为 13.
36是最低的可能总成本，因此返回它
示例 2:
输入: sentence = "apples and bananas taste great", k = 7
输出: 21
解释:
将 sentence 分成"apples", "and", "bananas", "taste", 和"great" 的成本为 (7 - 6)2 + (7 - 3)2 + (7 - 7)2 + (7 - 5)2 = 21.
21是最低的可能总成本，因此返回它
示例 3:
输入: sentence = "a", k = 5
输出: 0
解释:
最后一行的成本不包括在总成本中，而sentence只有一行，所以返回0
提示:
1 <= sentence.length <= 50001 <= k <= 5000sentence 中每个单词长度最大为 k.sentence 只包含小写字母和空格.sentence 不会以空格开头或结尾.sentence 中的单词以单个空格分隔.
解法
方法一：前缀和 + 记忆化搜索
思考
把单词序列拆成多行，除末行外代价为 \((k-\text{行宽})^2\)。单词数不大，但拆法指数级。从第 \(i\) 个词起的最小代价只依赖后缀。
前缀和 \(s\) 使区间词长与空格数可 \(O(1)\) 求得。若剩余整段落进末行则代价 \(0\)；否则枚举下一行终点 \(j\)，加上 \((k-m)^2\) 与 \(\textit{dfs}(j)\)。
记忆化后状态 \(n\)、转移 \(O(n)\)。
我们用一个数组 \(\textit{nums}\) 记录每个单词的长度，数组的长度记为 \(n\)。然后我们定义一个长度为 \(n + 1\) 的前缀和数组 \(s\)，其中 \(s[i]\) 表示前 \(i\) 个单词的长度之和。
接下来，我们设计一个函数 \(\textit{dfs}(i)\)，表示从第 \(i\) 个单词开始分隔句子的最小成本。那么答案为 \(\textit{dfs}(0)\)。
函数 \(\textit{dfs}(i)\) 的执行过程如下：
- 如果从第 \(i\) 个单词开始到最后一个单词的长度之和加上单词之间的空格数小于等于 \(k\)，那么这些单词可以放在最后一行，成本为 \(0\)。
- 否则，我们枚举下一个开始分隔的单词的位置 \(j\)，使得从第 \(i\) 个单词到第 \(j-1\) 个单词的长度之和加上单词之间的空格数小于等于 \(k\)。那么 \(\textit{dfs}(j)\) 表示从第 \(j\) 个单词开始分隔句子的最小成本，而 \((k - m)^2\) 表示将第 \(i\) 个单词到第 \(j-1\) 个单词放在一行的成本，其中 \(m\) 表示从第 \(i\) 个单词到第 \(j-1\) 个单词的长度之和加上单词之间的空格数。我们枚举所有的 \(j\)，取最小值即可。
答案即为 \(\textit{dfs}(0)\)。
为了避免重复计算，我们可以使用记忆化搜索。
时间复杂度 \(O(n^2)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为单词的个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | class Solution:
def minimumCost(self, sentence: str, k: int) -> int:
@cache
def dfs(i: int) -> int:
if s[n] - s[i] + n - i - 1 <= k:
return 0
ans = inf
j = i + 1
while j < n and (m := s[j] - s[i] + j - i - 1) <= k:
ans = min(ans, dfs(j) + (k - m) ** 2)
j += 1
return ans
nums = [len(s) for s in sentence.split()]
n = len(nums)
s = list(accumulate(nums, initial=0))
return dfs(0)
|
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 | class Solution {
private Integer[] f;
private int[] s;
private int k;
private int n;
public int minimumCost(String sentence, int k) {
this.k = k;
String[] words = sentence.split(" ");
n = words.length;
f = new Integer[n];
s = new int[n + 1];
for (int i = 0; i < n; ++i) {
s[i + 1] = s[i] + words[i].length();
}
return dfs(0);
}
private int dfs(int i) {
if (s[n] - s[i] + n - i - 1 <= k) {
return 0;
}
if (f[i] != null) {
return f[i];
}
int ans = Integer.MAX_VALUE;
for (int j = i + 1; j < n && s[j] - s[i] + j - i - 1 <= k; ++j) {
int m = s[j] - s[i] + j - i - 1;
ans = Math.min(ans, dfs(j) + (k - m) * (k - m));
}
return f[i] = 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 | class Solution {
public:
int minimumCost(string sentence, int k) {
istringstream iss(sentence);
vector<int> s = {0};
string w;
while (iss >> w) {
s.push_back(s.back() + w.size());
}
int n = s.size() - 1;
int f[n];
memset(f, -1, sizeof(f));
auto dfs = [&](this auto&& dfs, int i) -> int {
if (s[n] - s[i] + n - i - 1 <= k) {
return 0;
}
if (f[i] != -1) {
return f[i];
}
int ans = INT_MAX;
for (int j = i + 1; j < n && s[j] - s[i] + j - i - 1 <= k; ++j) {
int m = s[j] - s[i] + j - i - 1;
ans = min(ans, dfs(j) + (k - m) * (k - m));
}
return f[i] = ans;
};
return dfs(0);
}
};
|
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 | func minimumCost(sentence string, k int) int {
s := []int{0}
for _, w := range strings.Split(sentence, " ") {
s = append(s, s[len(s)-1]+len(w))
}
n := len(s) - 1
f := make([]int, n)
for i := range f {
f[i] = -1
}
var dfs func(int) int
dfs = func(i int) int {
if s[n]-s[i]+n-i-1 <= k {
return 0
}
if f[i] != -1 {
return f[i]
}
ans := math.MaxInt32
for j := i + 1; j < n && s[j]-s[i]+j-i-1 <= k; j++ {
m := s[j] - s[i] + j - i - 1
ans = min(ans, dfs(j)+(k-m)*(k-m))
}
f[i] = ans
return ans
}
return dfs(0)
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | function minimumCost(sentence: string, k: number): number {
const s: number[] = [0];
for (const w of sentence.split(' ')) {
s.push(s.at(-1)! + w.length);
}
const n = s.length - 1;
const f: number[] = Array(n).fill(-1);
const dfs = (i: number): number => {
if (s[n] - s[i] + n - i - 1 <= k) {
return 0;
}
if (f[i] !== -1) {
return f[i];
}
let ans = Infinity;
for (let j = i + 1; j < n && s[j] - s[i] + j - i - 1 <= k; ++j) {
const m = s[j] - s[i] + j - i - 1;
ans = Math.min(ans, dfs(j) + (k - m) ** 2);
}
return (f[i] = ans);
};
return dfs(0);
}
|
方法二：前缀和 + 动态规划
思考
把全部断行枚举一遍是指数级的。句子长度可以到 \(5000\)，单词很多时，下一行总是从下一个词开始试，递归深度就是单词数。从第 \(i\) 个词起的最小代价只依赖更靠后的词。于是用前缀和 \(O(1)\) 求出一行的宽度，令 \(f[i]\) 为从第 \(i\) 个词起的最小代价，剩余单词能放进末行则为 \(0\)，否则从右往左枚举下一行起点 \(j\)，加上 \((k-m)^2+f[j]\)。
用前缀和 \(s\) 记录单词长度， \(s[i]\) 为前 \(i\) 个单词的长度之和， \(n\) 为单词个数。设 \(f[i]\) 为从第 \(i\) 个单词开始排版的最小成本。从 \(i=n-1\) 递减到 \(0\)。若从 \(i\) 到末尾的单词长度再加上其间的空格数不超过 \(k\)，这些词可以放在最后一行， \(f[i]=0\)。否则枚举下一行的起点 \(j\)，使第 \(i\) 个到第 \(j-1\) 个单词连同空格的宽度 \(m\) 不超过 \(k\)，用 \((k-m)^2+f[j]\) 更新 \(f[i]\)。答案为 \(f[0]\)。
时间复杂度 \(O(n^2)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为单词的个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | class Solution:
def minimumCost(self, sentence: str, k: int) -> int:
nums = [len(w) for w in sentence.split()]
n = len(nums)
s = list(accumulate(nums, initial=0))
f = [0] * n
for i in range(n - 1, -1, -1):
if s[n] - s[i] + n - i - 1 <= k:
continue
ans = inf
j = i + 1
while j < n and (m := s[j] - s[i] + j - i - 1) <= k:
ans = min(ans, f[j] + (k - m) ** 2)
j += 1
f[i] = ans
return f[0]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | class Solution {
public int minimumCost(String sentence, int k) {
String[] words = sentence.split(" ");
int n = words.length;
int[] s = new int[n + 1];
for (int i = 0; i < n; ++i) {
s[i + 1] = s[i] + words[i].length();
}
int[] f = new int[n];
for (int i = n - 1; i >= 0; --i) {
if (s[n] - s[i] + n - i - 1 <= k) {
continue;
}
int ans = Integer.MAX_VALUE;
for (int j = i + 1; j < n && s[j] - s[i] + j - i - 1 <= k; ++j) {
int m = s[j] - s[i] + j - i - 1;
ans = Math.min(ans, f[j] + (k - m) * (k - m));
}
f[i] = ans;
}
return f[0];
}
}
|
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 | class Solution {
public:
int minimumCost(string sentence, int k) {
istringstream iss(sentence);
vector<int> s = {0};
string w;
while (iss >> w) {
s.push_back(s.back() + (int) w.size());
}
int n = s.size() - 1;
vector<int> f(n);
for (int i = n - 1; i >= 0; --i) {
if (s[n] - s[i] + n - i - 1 <= k) {
continue;
}
int ans = INT_MAX;
for (int j = i + 1; j < n && s[j] - s[i] + j - i - 1 <= k; ++j) {
int m = s[j] - s[i] + j - i - 1;
ans = min(ans, f[j] + (k - m) * (k - m));
}
f[i] = ans;
}
return f[0];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | func minimumCost(sentence string, k int) int {
s := []int{0}
for _, w := range strings.Split(sentence, " ") {
s = append(s, s[len(s)-1]+len(w))
}
n := len(s) - 1
f := make([]int, n)
for i := n - 1; i >= 0; i-- {
if s[n]-s[i]+n-i-1 <= k {
continue
}
ans := math.MaxInt32
for j := i + 1; j < n && s[j]-s[i]+j-i-1 <= k; j++ {
m := s[j] - s[i] + j - i - 1
ans = min(ans, f[j]+(k-m)*(k-m))
}
f[i] = ans
}
return f[0]
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | function minimumCost(sentence: string, k: number): number {
const s: number[] = [0];
for (const w of sentence.split(' ')) {
s.push(s.at(-1)! + w.length);
}
const n = s.length - 1;
const f: number[] = Array(n).fill(0);
for (let i = n - 1; i >= 0; --i) {
if (s[n] - s[i] + n - i - 1 <= k) {
continue;
}
let ans = Infinity;
for (let j = i + 1; j < n && s[j] - s[i] + j - i - 1 <= k; ++j) {
const m = s[j] - s[i] + j - i - 1;
ans = Math.min(ans, f[j] + (k - m) ** 2);
}
f[i] = ans;
}
return f[0];
}
|