418. Sentence Screen Fitting (Medium)
Given a rows x cols screen and a sentence represented by a list of non-empty words, find how many times the given sentence can be fitted on the screen.
Note:
- A word cannot be split into two lines.
- The order of words in the sentence must remain unchanged.
- Two consecutive words in a line must be separated by a single space.
- Total words in the sentence won't exceed 100.
- Length of each word is greater than 0 and won't exceed 10.
- 1 ≤ rows, cols ≤ 20,000.
Example 1:
Input:
rows = 2, cols = 8, sentence = ["hello", "world"]
Output:
1
Explanation:
hello---
world---
The character '-' signifies an empty space on the screen.
Example 2:
Input:
rows = 3, cols = 6, sentence = ["a", "bcd", "e"]
Output:
2
Explanation:
a-bcd-
e-a---
bcd-e-
The character '-' signifies an empty space on the screen.
Example 3:
Input:
rows = 4, cols = 5, sentence = ["I", "had", "apple", "pie"]
Output:
1
Explanation:
I-had
apple
pie-I
had--
The character '-' signifies an empty space on the screen.
Solution 1: DP 9ms
Update: As many people like this solution, let me explain by an example.
Say sentence=["abc", "de", "f], rows=4, and cols=6.
The screen should look like
"abc de"
"f abc "
"de f "
"abc de"
Consider the following repeating sentence string, with positions of the start character of each row on the screen.
"abc de f abc de f abc de f ..."
^ ^ ^ ^ ^
0 7 13 18 25
Our goal is to find the start position of the row next to the last row on the screen, which is 25 here. Since actually it's the length of everything earlier, we can get the answer by dividing this number by the length of (non-repeated) sentence string. Note that the non-repeated sentence string has a space at the end; it is "abc de f " in this example.
Here is how we find that position. In each iteration, we need to adjust start based on spaces either added or removed.
"abc de f abc de f abc de f ..." // start=0
012345 // start=start+cols+adjustment=0+6+1=7 (1 space removed in screen string)
012345 // start=7+6+0=13
012345 // start=13+6-1=18 (1 space added)
012345 // start=18+6+1=25 (1 space added)
012345
Hope this helps.
int wordsTyping(vector<string>& sentence, int rows, int cols) {
string sen;
for (auto word: sentence) sen += word+" ";
int len = sen.size(), start = 0;
cout << len << endl;
for (int i = 0; i < rows; ++i) {
start += cols;
if (sen[start%len] == ' ')
++start;
else
while (start > 0 && sen[(start-1)%len] != ' ') --start;
}
return start/len;
}
Solution 2: DP 13ms
First off, we can easily come up with a brute-force solution. The basic idea of optimized solution is that:
sub-problem: if there's a new line which is starting with certain index in sentence, what is the starting index of next line (nextIndex[]). BTW, we compute how many times the pointer in current line passes over the last index (times[]).
relation: ans += times[i], i = nextIndex[i], for _ in 0..<row. where i indicates what is the first word in the current line.
Time complexity: O(n*(cols/lenAverage)) + O(rows), where n is the length of sentence array, lenAverage is the average length of the words in the input array.
Well, It's not a typical "DP" problem and I am not even sure it is a "DP" problem. ( ͡° ͜ʖ ͡°)
int wordsTyping(vector<string>& sentence, int rows, int cols) {
int n = sentence.size();
// the start word of the next line w.r.t the position(idx) in sentence
// count how many times the partial sentence can fit in line with current start word
vector<int> nextIineIdx(n), count(n,0);
// sentence[i]: the start word in a line
for (int i = 0; i < n; ++i) {
int cur = i, curlen = 0;
while (curlen+sentence[cur].size() <= cols) {
curlen += sentence[cur++].size()+1;
if (cur == n) {
cur = 0;
++count[i];
}
nextIineIdx[i] = cur;
}
}
int cur = 0, ans = 0;
for (int i = 0; i < rows; ++i) {
ans += count[cur];
cur = nextIineIdx[cur];
}
return ans;
}
Solution 3: Hash Table 3ms
以后再看吧。。。