What is the best approach for Number of Lines To Write String?

Iterate through the string, accumulate widths from the array, and increment the line count whenever the 100-pixel limit is exceeded.

How do I handle characters that exactly reach 100 pixels?

When adding a character hits 100 pixels exactly, count it on the current line and start a new line with the next character.

Can the widths array contain values other than 2-10?

Constraints specify 2 <= widths[i] <= 10, so all characters will have widths within this range, simplifying accumulation logic.

Is the solution time complexity linear?

Yes, iterating through the string once gives O(N) time complexity and O(1) space since only counters are used.

Does this problem represent the Array plus String pattern?

Yes, it combines array lookups with sequential string processing to manage line widths, which is a classic Array plus String pattern.

#806

Easy

auto_awesome数组·string

LeetCode 题解工作台

写字符串需要的行数

我们要把给定的字符串 S 从左到右写到每一行上，每一行的最大宽度为100个单位，如果我们在写某个字母的时候会使这行超过了100 个单位，那么我们应该把这个字母写到下一行。我们给定了一个数组 widths ，这个数组 widths[0] 代表 'a' 需要的单位， widths[1] 代表 'b' 需…

数组字符串

题目描述

我们要把给定的字符串 S 从左到右写到每一行上，每一行的最大宽度为100个单位，如果我们在写某个字母的时候会使这行超过了100 个单位，那么我们应该把这个字母写到下一行。我们给定了一个数组 widths ，这个数组 widths[0] 代表 'a' 需要的单位， widths[1] 代表 'b' 需要的单位，...， widths[25] 代表 'z' 需要的单位。

现在回答两个问题：至少多少行能放下S，以及最后一行使用的宽度是多少个单位？将你的答案作为长度为2的整数列表返回。

示例 1:
输入: 
widths = [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
S = "abcdefghijklmnopqrstuvwxyz"
输出: [3, 60]
解释: 
所有的字符拥有相同的占用单位10。所以书写所有的26个字母，
我们需要2个整行和占用60个单位的一行。

示例 2:
输入: 
widths = [4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
S = "bbbcccdddaaa"
输出: [2, 4]
解释: 
除去字母'a'所有的字符都是相同的单位10，并且字符串 "bbbcccdddaa" 将会覆盖 9 * 10 + 2 * 4 = 98 个单位.
最后一个字母 'a' 将会被写到第二行，因为第一行只剩下2个单位了。
所以，这个答案是2行，第二行有4个单位宽度。

注:

字符串 S 的长度在 [1, 1000] 的范围。
S 只包含小写字母。
widths 是长度为 26的数组。
widths[i] 值的范围在 [2, 10]。

lightbulb

解题思路

方法一：模拟

我们定义两个变量 lines 和 last，分别表示行数和最后一行的宽度，初始时 lines = 1，last = 0。

遍历字符串 $s$ ，对于每个字符 $c$ ，计算其宽度 $w$ ，如果 $last + w \leq 100$ ，则将 $w$ 加到 last 上，否则行数 lines 加一，并且 last 重置为 $w$ 。

最后返回 lines 和 last 构成的数组。

时间复杂度 $O(n)$ ，其中 $n$ 为字符串 $s$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def numberOfLines(self, widths: List[int], s: str) -> List[int]:
        lines, last = 1, 0
        for w in map(lambda c: widths[ord(c) - ord("a")], s):
            if last + w <= 100:
                last += w
            else:
                lines += 1
                last = w
        return [lines, last]

speed

复杂度分析

指标	值
时间	O(S\text{
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Look for clear handling of line overflow when character width exceeds remaining space.
question_mark
Check if you accurately map letters to widths using the array index.
question_mark
Expect attention to edge cases where the last line may not reach the full 100 pixels.

warning

常见陷阱

外企场景

error
Off-by-one errors when a character exactly fills the line.
error
Incorrectly resetting current width after line increment.
error
Assuming all letters have equal width and ignoring the widths array.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow variable maximum line width instead of fixed 100 pixels.
arrow_right_alt
Return the pixel widths of all lines instead of just the last line.
arrow_right_alt
Handle strings that include uppercase letters or special characters with defined widths.

help

常见问题

外企场景

继续练习

#804 唯一摩尔斯密码词 #809 情感丰富的文字 #811 子域名访问计数