跳至主要內容

0806. 写字符串需要的行数

ITCharge大约 2 分钟

0806. 写字符串需要的行数open in new window

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

题目大意

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

要求:计算出能放下 ss 的最少行数,以及最后一行使用的宽度单位。

说明

  • 字符串 ss 的长度在 [1,1000][1, 1000] 的范围。
  • ss 只包含小写字母。
  • widthswidths 是长度为 2626 的数组。
  • widths[i]widths[i] 值的范围在 [2,10][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. 使用变量 linecntline\underline{}cnt 记录行数,使用变量 lastcntlast\underline{}cnt 记录最后一行使用的单位数。
  2. 遍历字符串,如果当前最后一行使用的单位数 + 当前字符需要的单位超过了 100100,则:
    1. 另起一行填充字符。(即行数加 11,最后一行使用的单位数为当前字符宽度)。
  3. 如果当前最后一行使用的单位数 + 当前字符需要的单位没有超过 100100,则:
    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(n)
  • 空间复杂度O(1)O(1)