2052. Minimum Cost to Separate Sentence Into Rows π
Description
You are given a string sentence
containing words separated by spaces, and an integer k
. Your task is to separate sentence
into rows where the number of characters in each row is at most k
. You may assume that sentence
does not begin or end with a space, and the words in sentence
are separated by a single space.
You can split sentence
into rows by inserting line breaks between words in sentence
. A word cannot be split between two rows. Each word must be used exactly once, and the word order cannot be rearranged. Adjacent words in a row should be separated by a single space, and rows should not begin or end with spaces.
The cost of a row with length n
is (k - n)2
, and the total cost is the sum of the costs for all rows except the last one.
- For example if
sentence = "i love leetcode"
andk = 12
:- Separating
sentence
into"i"
,"love"
, and"leetcode"
has a cost of(12 - 1)2 + (12 - 4)2 = 185
. - Separating
sentence
into"i love"
, and"leetcode"
has a cost of(12 - 6)2 = 36
. - Separating
sentence
into"i"
, and"love leetcode"
is not possible because the length of"love leetcode"
is greater thank
.
- Separating
Return the minimum possible total cost of separating sentence
into rows.
Example 1:
Input: sentence = "i love leetcode", k = 12 Output: 36 Explanation: Separating sentence into "i", "love", and "leetcode" has a cost of (12 - 1)2 + (12 - 4)2 = 185. Separating sentence into "i love", and "leetcode" has a cost of (12 - 6)2 = 36. Separating sentence into "i", "love leetcode" is not possible because "love leetcode" has length 13. 36 is the minimum possible total cost so return it.
Example 2:
Input: sentence = "apples and bananas taste great", k = 7 Output: 21 Explanation Separating sentence into "apples", "and", "bananas", "taste", and "great" has a cost of (7 - 6)2 + (7 - 3)2 + (7 - 7)2 + (7 - 5)2 = 21. 21 is the minimum possible total cost so return it.
Example 3:
Input: sentence = "a", k = 5 Output: 0 Explanation: The cost of the last row is not included in the total cost, and since there is only one row, return 0.
Constraints:
1 <= sentence.length <= 5000
1 <= k <= 5000
- The length of each word in
sentence
is at mostk
. sentence
consists of only lowercase English letters and spaces.sentence
does not begin or end with a space.- Words in
sentence
are separated by a single space.
Solutions
Solution 1: Prefix Sum + Memoized Search
We use an array $\textit{nums}$ to record the length of each word, and let the length of the array be $n$. Then we define a prefix sum array $\textit{s}$ of length $n + 1$, where $\textit{s}[i]$ represents the sum of the lengths of the first $i$ words.
Next, we design a function $\textit{dfs}(i)$, which represents the minimum cost of splitting the sentence starting from the $i$-th word. The answer is $\textit{dfs}(0)$.
The execution process of the function $\textit{dfs}(i)$ is as follows:
- If the sum of the lengths of the words from the $i$-th word to the last word plus the number of spaces between the words is less than or equal to $k$, then these words can be placed on the last line, and the cost is $0$.
- Otherwise, we enumerate the position $j$ of the next word to start splitting, such that the sum of the lengths of the words from the $i$-th word to the $(j-1)$-th word plus the number of spaces between the words is less than or equal to $k$. Then $\textit{dfs}(j)$ represents the minimum cost of splitting the sentence starting from the $j$-th word, and $(k - m)^2$ represents the cost of placing the words from the $i$-th word to the $(j-1)$-th word on one line, where $m$ represents the sum of the lengths of the words from the $i$-th word to the $(j-1)$-th word plus the number of spaces between the words. We enumerate all $j$ and take the minimum value.
The answer is $\textit{dfs}(0)$.
To avoid repeated calculations, we can use memoized search.
The time complexity is $O(n^2)$, and the space complexity is $O(n)$. Here, $n$ is the number of words.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
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 |
|
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 |
|
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 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|