跳转至

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 中的单词以单个空格分隔.

解法

方法一：记忆化搜索

 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:
        @cache
        def dfs(i):
            if s[-1] - s[i] + n - i - 1 <= k:
                return 0
            ans, j = inf, i + 1
            while j < n and (t := s[j] - s[i] + j - i - 1) <= k:
                ans = min(ans, (k - t) ** 2 + dfs(j))
                j += 1
            return ans

        t = [len(w) for w in sentence.split()]
        n = len(t)
        s = list(accumulate(t, 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
34
35
36
37
class Solution {
    private static final int INF = Integer.MAX_VALUE;
    private int[] memo;
    private int[] s;
    private int n;

    public int minimumCost(String sentence, int k) {
        String[] words = sentence.split(" ");
        n = words.length;
        s = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] + words[i].length();
        }
        memo = new int[n];
        Arrays.fill(memo, INF);
        return dfs(0, k);
    }

    private int dfs(int i, int k) {
        if (memo[i] != INF) {
            return memo[i];
        }
        if (s[n] - s[i] + n - i - 1 <= k) {
            memo[i] = 0;
            return 0;
        }
        int ans = INF;
        for (int j = i + 1; j < n; ++j) {
            int t = s[j] - s[i] + j - i - 1;
            if (t <= k) {
                ans = Math.min(ans, (k - t) * (k - t) + dfs(j, k));
            }
        }
        memo[i] = ans;
        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:
    const int inf = INT_MAX;
    int n;

    int minimumCost(string sentence, int k) {
        istringstream is(sentence);
        vector<string> words;
        string word;
        while (is >> word) words.push_back(word);
        n = words.size();
        vector<int> s(n + 1);
        for (int i = 0; i < n; ++i) s[i + 1] = s[i] + words[i].size();
        vector<int> memo(n, inf);
        return dfs(0, k, s, memo);
    }

    int dfs(int i, int k, vector<int>& s, vector<int>& memo) {
        if (memo[i] != inf) return memo[i];
        if (s[n] - s[i] + n - i - 1 <= k) {
            memo[i] = 0;
            return 0;
        }
        int ans = inf;
        for (int j = i + 1; j < n; ++j) {
            int t = s[j] - s[i] + j - i - 1;
            if (t <= k) ans = min(ans, (k - t) * (k - t) + dfs(j, k, s, memo));
        }
        memo[i] = ans;
        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
func minimumCost(sentence string, k int) int {
    words := strings.Split(sentence, " ")
    n := len(words)
    inf := math.MaxInt32
    s := make([]int, n+1)
    for i, word := range words {
        s[i+1] = s[i] + len(word)
    }
    memo := make([]int, n)
    for i := range memo {
        memo[i] = inf
    }
    var dfs func(int) int
    dfs = func(i int) int {
        if memo[i] != inf {
            return memo[i]
        }
        if s[n]-s[i]+n-i-1 <= k {
            memo[i] = 0
            return 0
        }
        ans := inf
        for j := i + 1; j < n; j++ {
            t := s[j] - s[i] + j - i - 1
            if t <= k {
                ans = min(ans, (k-t)*(k-t)+dfs(j))
            }
        }
        memo[i] = ans
        return ans
    }
    return dfs(0)
}

评论