题目

标题和出处

标题：写字符串需要的行数

出处：806. 写字符串需要的行数

难度

3 级

题目描述

要求

给你由小写英语字母组成的字符串 $\text{s}$ 和一个表示每个小写英语字母的宽度的像素数的数组 $\text{widths}$。特别地，$\text{widths[0]}$ 表示 $\text{‘a’}$ 的宽度，$\text{widths[1]}$ 表示 $\text{‘b’}$ 的宽度，以此类推。

你要将 $\text{s}$ 写在若干行中，每一行的最大长度不超过 $\text{100}$ 像素。从 $\text{s}$ 的第一个字符开始，在第一行写尽可能多的字母使得总宽度不超过 $\text{100}$ 像素。然后在第二行继续写尽可能多的 $\text{s}$ 中的字符。该过程持续到 $\text{s}$ 的全部字符都写完。

返回长度为 $\text{2}$ 的数组 $\text{result}$：

• $\text{result[0]}$ 是总行数；
• $\text{result[1]}$ 是最后一行的宽度的像素数。

示例

示例 1：

输入：$\text{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"}$
输出：$\text{[3,60]}$
解释：你可以按如下方法写 $\text{s}$：
$\text{abcdefghij // 100 像素}$
$\text{klmnopqrst // 100 像素}$
$\text{uvwxyz // 60 像素}$
一共有 $\text{3}$ 行，最后一行的宽度是 $\text{60}$ 像素。

示例 2：

输入：$\text{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"}$
输出：$\text{[2,4]}$
解释：你可以按如下方法写 $\text{s}$：
$\text{bbbcccdddaa // 98 像素}$
$\text{a // 4 像素}$
一共有 $\text{2}$ 行，最后一行的宽度是 $\text{4}$ 像素。

数据范围

• $\text{widths.length}=\text{26}$
• $\text{2}\le \text{widths[i]}\le \text{10}$
• $\text{1}\le \text{s.length}\le \text{1000}$
• $\text{s}$ 只包含小写英语字母

解法

思路和算法

这道题只需要模拟写字符串的过程，并计算使用的行数和当前行的宽度即可。

由于字符串 $s$ 的长度大于 $0$，因此至少需要 $1$ 行。

用 $\text{linesCount}$ 表示行数，$\text{curWidth}$ 表示当前行的宽度。初始化 $\text{linesCount}=1$ 和 $\text{curWidth}=0$。

从左到右遍历字符串 $s$，对于每个字符，获得该字符的宽度 $\text{width}$，进行如下操作：

• 如果 $\text{curWidth}+\text{width}\le 100$，则该字符可以写入当前行，因此 $\text{linesCount}$ 的值不变，将 $\text{curWidth}$ 的值增加 $\text{width}$；

• 如果 $\text{curWidth}+\text{width}>100$，则该字符不可以写入当前行，否则当前行的总宽度超过 $100$ 像素，因此该字符必须写在新的一行，将 $\text{linesCount}$ 的值加 $1$，将 $\text{curWidth}$ 的值设置为 $\text{width}$。

遍历结束之后，即有 $\text{result}[0]=\text{linesCount},\text{result}[1]=\text{curWidth}$。

上面的内容是解题过程。具体实现时，有一些细节问题需要考虑。

• 对于字符 $c$，其取值范围是 $\text{‘a’}$ 到 $\text{‘z’}$，$c-\text{‘a’}$ 的取值范围是 $0$ 到 $25$，和 $\text{widths}$ 的下标对应。因此，字符 $c$ 的宽度为 $\text{widths}[c-\text{‘a’}]$。

• 题目中明确说明了每一行最多 $100$ 像素，因此可以在代码中使用数字 $100$ 表示每一行的最大宽度。更好的做法是声明常量 $\text{MAX\_WIDTH}$，将该常量的值设为 $100$，然后用该常量表示每一行的最大宽度。使用常量的好处是常量名称可以体现含义，增加代码的可读性，而且更有利于程序的可扩展性。

代码

class Solution {
    public int[] numberOfLines(int[] widths, String s) {
        final int MAX_WIDTH = 100;
        int linesCount = 1, curWidth = 0;
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            int width = widths[c - 'a'];
            if (curWidth + width <= MAX_WIDTH) {
                curWidth += width;
            } else {
                linesCount++;
                curWidth = width;
            }
        }
        return new int[]{linesCount, curWidth};
    }
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是字符串 $s$ 的长度。需要遍历字符串 $s$ 一次。

• 空间复杂度：$O(1)$。