文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給你一個 rows x cols 的屏幕和一個用 非空 的單詞列表組成的句子，請你計算出給定句子可以在屏幕上完整顯示的次數。

注意：
一個單詞不能拆分成兩行。
單詞在句子中的順序必須保持不變。
在一行中 的兩個連續單詞必須用一個空格符分隔。
句子中的單詞總量不會超過 100。
每個單詞的長度大于 0 且不會超過 10。
1 ≤ rows, cols ≤ 20,000.

示例 1： 輸入： rows = 2, cols = 8, 句子 sentence = ["hello", "world"] 輸出： 1 解釋： hello--- world--- 字符 '-' 表示屏幕上的一個空白位置。示例 2： 輸入： rows = 3, cols = 6, 句子 sentence = ["a", "bcd", "e"] 輸出： 2 解釋： a-bcd- e-a--- bcd-e- 字符 '-' 表示屏幕上的一個空白位置。示例 3： 輸入： rows = 4, cols = 5, 句子 sentence = ["I", "had", "apple", "pie"] 輸出： 1 解釋： I-had apple pie-I had-- 字符 '-' 表示屏幕上的一個空白位置。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/sentence-screen-fitting
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

• 參考大佬的題解
• 先看看1行能不能放下完整的句子
• 然后不能放下完整句子的空位，從 i 單詞開始放（i=0…n-1），下一行的開頭是哪個單詞

class Solution { public:int wordsTyping(vector<string>& sentence, int rows, int cols) {int n = sentence.size(), i, j, len = 0, ans = 0;vector<int> wordlen(sentence.size());for(i = 0; i < n; ++i){len += sentence[i].size()+1;wordlen[i] = sentence[i].size();}len--;//一個句子的長度if(cols >= len)//能放下完整的句子{ans += cols/(len+1)*rows;//帶一個空格能放下幾個句子cols = cols%(len+1);//只用考慮剩余的不完整空格if(cols%(len+1) == len)//不帶空格正好還有一個位置{ans += rows;return ans;}}vector<int> dp(n);//每行從i單詞開始填，可以填到哪個單詞for(i = 0 ;i < n; i++){j = i;len = 0;while(len+wordlen[j] <= cols){len += wordlen[j]+1;//+1是空格j = (j+1)%n;}dp[i] = j;//i單詞開始放，放完該行可以到j單詞（不含j）}for(i = 0, j = 0; i < rows; i++){if(dp[j] < j)//放滿了一行，dp[j]跑到 j 前面去了ans++;j = dp[j];//下一行從dp[j]單詞開始放}return ans;} };

0 ms 7.6 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 418. 屏幕可显示句子的数量（DP）*的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。