# 2052. Minimum Cost to Separate Sentence Into Rows¶

• Time: $O(n^2)$, where $n = |\texttt{words}|$
• Space: $O(n)$
  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 38 39 40 41 class Solution { public: int minimumCost(string sentence, int k) { if (sentence.length() <= k) return 0; vector words = getWords(sentence); // dp[i] := the minimum cost of the first i words vector dp(words.size() + 1); for (int i = 1; i <= words.size(); ++i) { int n = words[i - 1].length(); // the length of the current row dp[i] = dp[i - 1] + (k - n) * (k - n); // Gradually add words[j - 1], words[j - 2], .... for (int j = i - 1; j > 0; --j) { n += words[j - 1].length() + 1; if (n > k) break; dp[i] = min(dp[i], dp[j - 1] + (k - n) * (k - n)); } } int lastRowLen = words.back().length(); int i = words.size() - 2; while (i > 0 && lastRowLen + words[i].length() + 1 <= k) lastRowLen += words[i--].length() + 1; return *min_element(dp.begin() + i + 1, dp.end()); } private: vector getWords(const string& sentence) { vector words; istringstream iss(sentence); for (string token; iss >> token;) words.push_back(token); return words; } }; 
  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 class Solution { public int minimumCost(String sentence, int k) { if (sentence.length() <= k) return 0; String[] words = sentence.split(" "); // dp[i] := the minimum cost of the first i words int[] dp = new int[words.length + 1]; for (int i = 1; i <= words.length; ++i) { int n = words[i - 1].length(); // the length of the current row dp[i] = dp[i - 1] + (k - n) * (k - n); // Gradually add words[j - 1], words[j - 2], .... for (int j = i - 1; j > 0; --j) { n += words[j - 1].length() + 1; if (n > k) break; dp[i] = Math.min(dp[i], dp[j - 1] + (k - n) * (k - n)); } } int lastRowLen = words[words.length - 1].length(); int i = words.length - 2; while (i > 0 && lastRowLen + words[i].length() + 1 <= k) lastRowLen += words[i--].length(); return Arrays.stream(dp, i + 1, words.length).min().getAsInt(); } } 
  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 class Solution: def minimumCost(self, sentence: str, k: int) -> int: if len(sentence) <= k: return 0 words = sentence.split() # dp[i] := the minimum cost of the first i words dp = [0] * (len(words) + 1) for i in range(1, len(words) + 1): n = len(words[i - 1]) # the length of the current row dp[i] = dp[i - 1] + (k - n)**2 # Gradually add words[j - 1], words[j - 2], .... for j in range(i - 1, 0, -1): n += len(words[j - 1]) + 1 if n > k: break dp[i] = min(dp[i], dp[j - 1] + (k - n)**2) lastRowLen = len(words[-1]) i = len(words) - 2 # Greedily put words into last row while i > 0 and lastRowLen + len(words[i]) + 1 <= k: lastRowLen += len(words[i]) + 1 i -= 1 return min(dp[i + 1:len(words)])