Skip to content

Latest commit

 

History

History
268 lines (220 loc) · 9.56 KB

README_EN.md

File metadata and controls

268 lines (220 loc) · 9.56 KB
comments difficulty edit_url tags
true
Medium
Array
Dynamic Programming

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" and k = 12: 
    <ul>
	<li>Separating <code>sentence</code> into <code>&quot;i&quot;</code>, <code>&quot;love&quot;</code>, and <code>&quot;leetcode&quot;</code> has a cost of <code>(12 - 1)<sup>2</sup> + (12 - 4)<sup>2</sup> = 185</code>.</li>
	<li>Separating <code>sentence</code> into <code>&quot;i love&quot;</code>, and <code>&quot;leetcode&quot;</code> has a cost of <code>(12 - 6)<sup>2</sup> = 36</code>.</li>
	<li>Separating <code>sentence</code> into <code>&quot;i&quot;</code>, and <code>&quot;love leetcode&quot;</code> is not possible because the length of <code>&quot;love leetcode&quot;</code> is greater than <code>k</code>.</li>
</ul>
</li>

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 most k.
  • 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.

Python3

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)

Java

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;
    }
}

C++

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);
    }
};

Go

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)
}

TypeScript

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);
}