A
A
Algorithm Practice
Search…
A
A
Algorithm Practice
Introduction
Lintcode
Leetcode
Math
Tree
Graph
Two Pointers
Linked List
Topological Sort
Hash Table
Trie
Sort
Binary Search
Heap
Breadth First Search
Stack
Backtracking
Dynamic Programming
LIS
Longest Common Subsequence
Interval DP
Knapsack Problem
10 Regular Expression Matching
32 Longest Valid Parentheses
44 Wildcard Matching
53 Maximum Subarray
62 Unique Paths
63 Unique Paths II
64 Minimum Path Sum
70 Climbing Stairs
85 Maximal Rectangle
87 Scramble String
91 Decode Ways
95 Unique Binary Search Trees II
96 Unique Binary Search Trees
97 Interleaving String
120 Triangle
121 Best Time to Buy and Sell Stock
122 Best Time to Buy and Sell Stock II
123 Best Time to Buy and Sell Stock III
139 Word Break
140 Word Break II
152 Maximum Product Subarray
174 Dungeon Game
188 Best Time to Buy and Sell Stock IV
198 House Robber
213 House Robber II
221 Maximal Square
238 Product of Array Except Self
256 Paint House
264 Ugly Number II
265 Paint House II
276 Paint Fence
279 Perfect Squares
303 Range Sum Query - Immutable
304 Range Sum Query 2D - Immutable
309 Best Time to Buy and Sell Stock with Cooldown
321 Create Maximum Number
338 Counting Bits
343 Integer Break
361 Bomb Enemy
363 Max Sum of Rectangle No Larger Than K
368 Largest Divisible Subset
403 Frog Jump
410 Split Array Largest Sum
413 Arithmetic Slices
418 Sentence Screen Fitting
446 Arithmetic Slices II - Subsequence
464 Can I Win
466 Count The Repetitions
467 Unique Substrings in Wraparound String
471 Encode String with Shortest Length
514 Freedom Trail
517 Super Washing Machines
523 Continuous Subarray Sum
552 Student Attendance Record II
562 Longest Line of Consecutive One in Matrix
568 Maximum Vacation Days
576 Out of Boundary Paths
600 Non-negative Integers without Consecutive Ones
629 K Inverse Pairs Array
638 Shopping Offers
639 Decode Ways II
650 2 Keys Keyboard
651 4 Keys Keyboard
656 Coin Path
688 Knight Probability in Chessboard
689 Maximum Sum of 3 Non-Overlapping Subarrays
691 Stickers to Spell Word
698 Partition to K Equal Sum Subsets
714 Best Time to Buy and Sell Stock with Transaction Fee
718 Maximum Length of Repeated Subarray
727 Minimum Window Subsequence
730 Count Different Palindromic Subsequences
740 Delete and Earn
741 Cherry Pickup
746 Min Cost Climbing Stairs
750 Number Of Corner Rectangles
764 Largest Plus Sign
787 Cheapest Flights Within K Stops
790 Domino and Tromino Tiling
801 Minimum Swaps To Make Sequences Increasing
Union Find
Scan Line
String
Reservoir Sampling
Recursion
Google
Powered By
GitBook
418 Sentence Screen Fitting
418.
Sentence Screen Fitting
1. Question
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:
1.
A word cannot be split into two lines.
2.
The order of words in the sentence must remain unchanged.
3.
Two consecutive words
in a line
must be separated by a single space.
4.
Total words in the sentence won't exceed 100.
5.
Length of each word is greater than 0 and won't exceed 10.
6.
1 ≤ rows, cols ≤ 20,000.
Example 1:
1
Input: rows = 2, cols = 8, sentence = ["hello", "world"]
2
3
Output: 1
4
5
Explanation:
6
hello---
7
world---
8
9
The character '-' signifies an empty space on the screen.
Copied!
Example 2:
1
Input: rows = 3, cols = 6, sentence = ["a", "bcd", "e"]
2
3
Output: 2
4
5
6
Explanation:
7
a-bcd-
8
e-a---
9
bcd-e-
10
11
The character '-' signifies an empty space on the screen.
Copied!
Example 3:
1
Input: rows = 4, cols = 5, sentence = ["I", "had", "apple", "pie"]
2
3
Output: 1
4
5
6
Explanation:
7
I-had
8
apple
9
pie-I
10
had--
11
12
The character '-' signifies an empty space on the screen.
Copied!
2. Implementation
思路: 这道题是给定一个每个单词以空格隔开的句子,要求用多少这个句子才能完全fit上 row * col的screen, 一个单词不能分布在不同的两行。所以我们先得到这个句子用空格隔开后的长度len,然后用start这个变量判断每行最后一个空格在哪,最后的结果就是start / len
1
class
Solution
{
2
public
int
wordsTyping
(
String
[]
sentence
,
int
rows
,
int
cols
)
{
3
String
s
=
""
;
4
5
for
(
String
word
:
sentence
)
{
6
s
+=
word
+
" "
;
7
}
8
9
int
len
=
s
.
length
();
10
int
start
=
0
;
11
12
for
(
int
i
=
0
;
i
<
rows
;
i
++
)
{
13
start
+=
cols
;
14
if
(
s
.
charAt
(
start
%
len
)
==
' '
)
{
15
++
start
;
16
}
17
else
{
18
while
(
start
>
0
&&
s
.
charAt
((
start
-
1
)
%
len
)
!=
' '
)
{
19
--
start
;
20
}
21
}
22
}
23
return
start
/
len
;
24
}
25
}
Copied!
3. Time & Space Complexity
时间复杂度O(n), 空间复杂度O(n)
Previous
413 Arithmetic Slices
Next
446 Arithmetic Slices II - Subsequence
Last modified
2yr ago
Copy link
Contents
418. Sentence Screen Fitting
1. Question
2. Implementation
3. Time & Space Complexity