LeetCode 418: Sentence Screen Fitting (Row Jump via Precomputed Next Index)
LeetCode 418StringDPToday we solve LeetCode 418 - Sentence Screen Fitting.
Source: https://leetcode.com/problems/sentence-screen-fitting/
English
Problem Summary
Given a sentence (array of words), number of rows, and number of columns, place words left to right on each row with one space between adjacent words. Return how many times the whole sentence can be fitted on the screen.
Key Insight
For each possible starting word index i, precompute two values for one row: next starting index after filling that row, and how many complete sentence loops are consumed in that row. Then simulate rows jumps in O(rows).
Algorithm
- Let n = sentence.length.
- For each i in [0, n), greedily place words while remaining columns allow.
- Record nextIdx[i] and addCount[i].
- Start from index 0, iterate each row: add addCount[cur], move to nextIdx[cur].
Complexity Analysis
Precompute: O(n * avgWordsPerRow).
Simulation: O(rows).
Space: O(n).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int wordsTyping(String[] sentence, int rows, int cols) {
int n = sentence.length;
int[] nextIdx = new int[n];
int[] addCount = new int[n];
for (int i = 0; i < n; i++) {
int c = cols;
int j = i;
int cnt = 0;
while (c >= sentence[j].length()) {
c -= sentence[j].length() + 1;
j++;
if (j == n) {
j = 0;
cnt++;
}
}
nextIdx[i] = j;
addCount[i] = cnt;
}
int ans = 0;
int cur = 0;
for (int r = 0; r < rows; r++) {
ans += addCount[cur];
cur = nextIdx[cur];
}
return ans;
}
}func wordsTyping(sentence []string, rows int, cols int) int {
n := len(sentence)
nextIdx := make([]int, n)
addCount := make([]int, n)
for i := 0; i < n; i++ {
c := cols
j := i
cnt := 0
for c >= len(sentence[j]) {
c -= len(sentence[j]) + 1
j++
if j == n {
j = 0
cnt++
}
}
nextIdx[i] = j
addCount[i] = cnt
}
ans, cur := 0, 0
for r := 0; r < rows; r++ {
ans += addCount[cur]
cur = nextIdx[cur]
}
return ans
}class Solution {
public:
int wordsTyping(vector<string>& sentence, int rows, int cols) {
int n = sentence.size();
vector<int> nextIdx(n), addCount(n);
for (int i = 0; i < n; i++) {
int c = cols, j = i, cnt = 0;
while (c >= (int)sentence[j].size()) {
c -= (int)sentence[j].size() + 1;
j++;
if (j == n) {
j = 0;
cnt++;
}
}
nextIdx[i] = j;
addCount[i] = cnt;
}
int ans = 0, cur = 0;
for (int r = 0; r < rows; r++) {
ans += addCount[cur];
cur = nextIdx[cur];
}
return ans;
}
};class Solution:
def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:
n = len(sentence)
next_idx = [0] * n
add_count = [0] * n
for i in range(n):
c = cols
j = i
cnt = 0
while c >= len(sentence[j]):
c -= len(sentence[j]) + 1
j += 1
if j == n:
j = 0
cnt += 1
next_idx[i] = j
add_count[i] = cnt
ans = 0
cur = 0
for _ in range(rows):
ans += add_count[cur]
cur = next_idx[cur]
return ans/**
* @param {string[]} sentence
* @param {number} rows
* @param {number} cols
* @return {number}
*/
var wordsTyping = function(sentence, rows, cols) {
const n = sentence.length;
const nextIdx = new Array(n).fill(0);
const addCount = new Array(n).fill(0);
for (let i = 0; i < n; i++) {
let c = cols;
let j = i;
let cnt = 0;
while (c >= sentence[j].length) {
c -= sentence[j].length + 1;
j += 1;
if (j === n) {
j = 0;
cnt += 1;
}
}
nextIdx[i] = j;
addCount[i] = cnt;
}
let ans = 0;
let cur = 0;
for (let r = 0; r < rows; r++) {
ans += addCount[cur];
cur = nextIdx[cur];
}
return ans;
};中文
题目概述
给定句子数组 sentence、行数 rows 和列数 cols。每行从左到右放单词，相邻单词之间必须有一个空格。求整句最多能完整放下多少次。
核心思路
对每个可能的起始单词下标 i，预处理“这一行填完后下一个起点是哪个单词”，以及“这一行贡献了几个完整句子”。之后按行跳转，累计贡献值即可。
算法步骤
- 设 n = sentence.length。
- 枚举起点 i，在 cols 里尽量多放单词，得到 nextIdx[i] 与 addCount[i]。
- 从起点 0 出发，循环 rows 行：答案加上 addCount[cur]，再跳到 nextIdx[cur]。
复杂度分析
预处理复杂度：O(n * 每行可放单词数)。
按行模拟：O(rows)。
空间复杂度：O(n)。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int wordsTyping(String[] sentence, int rows, int cols) {
int n = sentence.length;
int[] nextIdx = new int[n];
int[] addCount = new int[n];
for (int i = 0; i < n; i++) {
int c = cols;
int j = i;
int cnt = 0;
while (c >= sentence[j].length()) {
c -= sentence[j].length() + 1;
j++;
if (j == n) {
j = 0;
cnt++;
}
}
nextIdx[i] = j;
addCount[i] = cnt;
}
int ans = 0;
int cur = 0;
for (int r = 0; r < rows; r++) {
ans += addCount[cur];
cur = nextIdx[cur];
}
return ans;
}
}func wordsTyping(sentence []string, rows int, cols int) int {
n := len(sentence)
nextIdx := make([]int, n)
addCount := make([]int, n)
for i := 0; i < n; i++ {
c := cols
j := i
cnt := 0
for c >= len(sentence[j]) {
c -= len(sentence[j]) + 1
j++
if j == n {
j = 0
cnt++
}
}
nextIdx[i] = j
addCount[i] = cnt
}
ans, cur := 0, 0
for r := 0; r < rows; r++ {
ans += addCount[cur]
cur = nextIdx[cur]
}
return ans
}class Solution {
public:
int wordsTyping(vector<string>& sentence, int rows, int cols) {
int n = sentence.size();
vector<int> nextIdx(n), addCount(n);
for (int i = 0; i < n; i++) {
int c = cols, j = i, cnt = 0;
while (c >= (int)sentence[j].size()) {
c -= (int)sentence[j].size() + 1;
j++;
if (j == n) {
j = 0;
cnt++;
}
}
nextIdx[i] = j;
addCount[i] = cnt;
}
int ans = 0, cur = 0;
for (int r = 0; r < rows; r++) {
ans += addCount[cur];
cur = nextIdx[cur];
}
return ans;
}
};class Solution:
def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:
n = len(sentence)
next_idx = [0] * n
add_count = [0] * n
for i in range(n):
c = cols
j = i
cnt = 0
while c >= len(sentence[j]):
c -= len(sentence[j]) + 1
j += 1
if j == n:
j = 0
cnt += 1
next_idx[i] = j
add_count[i] = cnt
ans = 0
cur = 0
for _ in range(rows):
ans += add_count[cur]
cur = next_idx[cur]
return ans/**
* @param {string[]} sentence
* @param {number} rows
* @param {number} cols
* @return {number}
*/
var wordsTyping = function(sentence, rows, cols) {
const n = sentence.length;
const nextIdx = new Array(n).fill(0);
const addCount = new Array(n).fill(0);
for (let i = 0; i < n; i++) {
let c = cols;
let j = i;
let cnt = 0;
while (c >= sentence[j].length) {
c -= sentence[j].length + 1;
j += 1;
if (j === n) {
j = 0;
cnt += 1;
}
}
nextIdx[i] = j;
addCount[i] = cnt;
}
let ans = 0;
let cur = 0;
for (let r = 0; r < rows; r++) {
ans += addCount[cur];
cur = nextIdx[cur];
}
return ans;
};
Comments