418.Sentence Screen Fitting
Tags: [DP], [memo], [trick]
Com: {g}
Link: https://leetcode.com/problems/sentence-screen-fitting/#/description
Given a rows x colsscreen 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:
class Solution(object):
def wordsTyping(self, sentence, rows, cols):
"""
:type sentence: List[str]
:type rows: int
:type cols: int
:rtype: int
"""
if not sentence or not rows or not cols:
return 0
s = ' '.join(sentence) + ' '
size = len(s)
start = 0
for _ in xrange(rows):
start += cols
if s[start % size] == ' ':
start += 1
continue
while start >= 0 and s[(start - 1) % size] != ' ':
start -= 1
return start / size
Revelation:
Note:
- Time complexity = O(n + rows * n) = O(rows * n), n is the number of words in sentence.
Solution:
class Solution(object):
def wordsTyping(self, sentence, rows, cols):
"""
:type sentence: List[str]
:type rows: int
:type cols: int
:rtype: int
"""
if not sentence or not rows or not cols:
return 0
num_of_w = len(sentence)
next_row_head_index = [0 for _ in xrange(num_of_w)]
times = [0 for _ in xrange(num_of_w)]
for i in xrange(num_of_w):
appearance_times = 0
c_counter = 0
w_counter = 0
curr = i
while c_counter + len(sentence[curr]) + ((w_counter + 1) - 1) <= cols:
c_counter += len(sentence[curr])
w_counter += 1
curr += 1
if curr == num_of_w:
appearance_times += 1
curr = 0
next_row_head_index[i] = curr
times[i] = appearance_times
result = 0
curr = 0
for _ in xrange(rows):
result += times[curr]
curr = next_row_head_index[curr]
return result
Revelation:
- The main idea is that preprocessing, we try to calculate that if the current word is the head of the row, what's the next row's head word, and what's the appearance times, we think each word may be the row's head, so we put each word in the head of the row, and calculate its next row's head and the appearance times, and store them. Because we know the first's row's head word's index is 0, then we start from there, to calculate row by row.
Note:
- Time complexity = O(n * cols / min([len(w) for w in sentence]) + rows), n is the number of words in sentence.
Time Limited Exceeded
class Solution(object):
def wordsTyping(self, sentence, rows, cols):
"""
:type sentence: List[str]
:type rows: int
:type cols: int
:rtype: int
"""
if not sentence or not rows or not cols:
return 0
size = len(sentence)
times = 0
index = 0
row = 0
while row < rows:
c_counter = 0
w_counter = 0
while True:
curr = sentence[index]
c_counter += len(curr)
w_counter += 1
curr_len = c_counter + (w_counter - 1)
if curr_len > cols:
break
index += 1
if index == size:
times += 1
index = 0
row += 1
return times
Note:
- Time complexity = O(rows * cols / min([len(w) for w in sentence])). Not sure why the above algorithm is slower than the first solution.