You are given a string sentence and an integer k. The goal is to split the sentence into multiple rows such that each row contains a contiguous sequence of words from the original sentence, and the total length of each row does not exceed k (including spaces between words).
For each row except the last, you must pay a cost equal to (k - length of the row)^2. The last row incurs no cost regardless of its length. Your task is to determine the minimum total cost required to split the sentence into rows under these conditions.
Constraints:
sentence ≤ 1000k ≤ 1000At first glance, this problem seems similar to text justification or word wrapping. A brute-force approach would be to try every possible way to split the sentence and compute the cost for each configuration, but this quickly becomes impractical as the number of words grows.
To optimize, we notice that the problem has overlapping subproblems: the minimum cost to arrange the rest of the sentence after a certain word can be reused if we encounter the same sub-sentence again. This hints at a dynamic programming (DP) approach, where we store the minimum cost for each possible starting word index.
The key is to try every possible way to break the sentence at each word, calculate the cost for the current row, and recursively solve for the rest. We keep track of the minimum cost encountered.
We use a dynamic programming strategy to efficiently compute the minimum cost:
sentence into a list of words.
dp[i] represent the minimum cost to arrange the words starting from index i.
i is at the end of the words list, the cost is 0 (no words left).
j (starting from i), check if the length of words from i to j fits in a row (including spaces). If it does, calculate the cost for this row:
j is the last word, cost is 0.(k - row_length)^2 plus dp[j+1].dp[0], the minimum cost to arrange all words.
This approach ensures we only compute each subproblem once, making it efficient even for large sentences.
Example:
sentence = "hello world leetcode", k = 12
The minimum cost is achieved by splitting as ["hello world", "leetcode"], with total cost = 1.
Brute-force approach: For each word, we can split at every possible position, leading to exponential combinations (O(2^n)). This is not feasible for large n.
Optimized DP approach:
O(n) subproblems (one for each word index).O(n) possible splits (from current index to end).O(n^2), where n is the number of words.O(n) for the DP array or memoization table.
The problem is a variation of the classic word wrap or text justification problem, where we seek to minimize the cost of splitting a sentence into rows of at most k characters. By using dynamic programming and memoization, we efficiently compute the minimum cost for each sub-sentence, avoiding redundant calculations. The solution demonstrates the power of DP in optimizing problems with overlapping subproblems and optimal substructure.
from functools import lru_cache
class Solution:
def minimumCost(self, sentence: str, k: int) -> int:
words = sentence.split()
n = len(words)
@lru_cache(maxsize=None)
def dp(i):
if i == n:
return 0
min_cost = float('inf')
length = 0
for j in range(i, n):
length += len(words[j])
if j > i:
length += 1 # space
if length > k:
break
if j == n - 1:
cost = 0
else:
cost = (k - length) ** 2
min_cost = min(min_cost, cost + dp(j + 1))
return min_cost
return dp(0)
#include <vector>
#include <string>
#include <climits>
using namespace std;
class Solution {
public:
int minimumCost(string sentence, int k) {
vector<string> words;
int n = 0;
size_t pos = 0, found;
while ((found = sentence.find(' ', pos)) != string::npos) {
words.push_back(sentence.substr(pos, found - pos));
pos = found + 1;
}
words.push_back(sentence.substr(pos));
n = words.size();
vector<int> dp(n + 1, -1);
function<int(int)> solve = [&](int i) {
if (i == n) return 0;
if (dp[i] != -1) return dp[i];
int min_cost = INT_MAX;
int length = 0;
for (int j = i; j < n; ++j) {
length += words[j].length();
if (j > i) length += 1;
if (length > k) break;
int cost = (j == n - 1) ? 0 : (k - length) * (k - length);
int total = cost + solve(j + 1);
if (total < min_cost) min_cost = total;
}
dp[i] = min_cost;
return min_cost;
};
return solve(0);
}
};
import java.util.*;
class Solution {
public int minimumCost(String sentence, int k) {
String[] words = sentence.split(" ");
int n = words.length;
Integer[] memo = new Integer[n + 1];
return dp(0, words, k, memo);
}
private int dp(int i, String[] words, int k, Integer[] memo) {
int n = words.length;
if (i == n) return 0;
if (memo[i] != null) return memo[i];
int minCost = Integer.MAX_VALUE;
int length = 0;
for (int j = i; j < n; ++j) {
length += words[j].length();
if (j > i) length += 1;
if (length > k) break;
int cost = (j == n - 1) ? 0 : (k - length) * (k - length);
int total = cost + dp(j + 1, words, k, memo);
if (total < minCost) minCost = total;
}
memo[i] = minCost;
return minCost;
}
}
/**
* @param {string} sentence
* @param {number} k
* @return {number}
*/
var minimumCost = function(sentence, k) {
const words = sentence.split(' ');
const n = words.length;
const memo = new Array(n + 1).fill(undefined);
function dp(i) {
if (i === n) return 0;
if (memo[i] !== undefined) return memo[i];
let minCost = Infinity;
let length = 0;
for (let j = i; j < n; ++j) {
length += words[j].length;
if (j > i) length += 1;
if (length > k) break;
let cost = (j === n - 1) ? 0 : Math.pow(k - length, 2);
minCost = Math.min(minCost, cost + dp(j + 1));
}
memo[i] = minCost;
return minCost;
}
return dp(0);
};