跳转至

2052. 将句子分隔成行的最低成本 🔒

题目描述

给定一个由空格分隔的单词组成的字符串 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 <= 5000
  • 1 <= k <= 5000
  • sentence 中每个单词长度最大为 k.
  • sentence 只包含小写字母和空格.
  • sentence 不会以空格开头或结尾.
  • sentence 中的单词以单个空格分隔.

解法

方法一：前缀和 + 记忆化搜索

我们用一个数组 $\textit{nums}$ 记录每个单词的长度，数组的长度记为 $n$。然后我们定义一个长度为 $n + 1$ 的前缀和数组 $\textit{s}$，其中 $\textit{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 = [&](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(dfs, j) + (k - m) * (k - m));
            }
            return f[i] = ans;
        };
        return dfs(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);
}

评论