0806. 写字符串需要的行数

• 标签：数组、字符串
• 难度：简单

题目链接

• 0806. 写字符串需要的行数 - 力扣

题目大意

描述：给定一个数组 $widths$，其中 $words[0]$ 代表 'a' 需要的单位，$words[1]$ 代表 'b' 需要的单位，…，$words[25]$ 代表 'z' 需要的单位。再给定一个字符串 $s$，现在需要将字符串 $s$ 从左到右写到每一行上，每一行的最大宽度为 $100$ 个单位，如果在写某个字符的时候使改行超过了 $100$ 个单位，那么我们应该将这个字母写到下一行。

要求：计算出能放下 $s$ 的最少行数，以及最后一行使用的宽度单位。

说明：

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

示例：

• 示例 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个单位宽度。

解题思路

思路 1：模拟

1. 使用变量 $line\underline{\hspace{0.5em}}cnt$ 记录行数，使用变量 $last\underline{\hspace{0.5em}}cnt$ 记录最后一行使用的单位数。
2. 遍历字符串，如果当前最后一行使用的单位数 + 当前字符需要的单位超过了 $100$，则：
   1. 另起一行填充字符。（即行数加 $1$，最后一行使用的单位数为当前字符宽度）。
3. 如果当前最后一行使用的单位数 + 当前字符需要的单位没有超过 $100$，则：
   1. 在当前行填充字符。（即最后一行使用的单位数累加上当前字符宽度）。

思路 1：代码

class Solution:
    def numberOfLines(self, widths: List[int], s: str) -> List[int]:
        line_cnt, last_cnt = 1, 0
        for ch in s:
            width = widths[ord(ch) - ord('a')]
            if last_cnt + width > 100:
                line_cnt += 1
                last_cnt = width
            else:
                last_cnt += width
                
        return [line_cnt, last_cnt]

思路 1：复杂度分析

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