写字符串需要的行数

标签: 数组 字符串

难度: Easy

我们要把给定的字符串 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]。

Submission

运行时间: 12 ms

内存: 16.0 MB

from typing import List

class Solution:
    def numberOfLines(self, widths: List[int], s: str) -> List[int]:
        lines = 1
        current_width = 0
        
        for char in s:
            char_width = widths[ord(char) - ord('a')]
            if current_width + char_width > 100:
                lines += 1
                current_width = char_width
            else:
                current_width += char_width
        
        return [lines, current_width]

Explain

该题解采用了一次遍历字符串的方法。它维护两个变量：lines 表示需要的行数，current_width 表示当前行已经使用的宽度。遍历字符串中的每个字符，计算该字符需要的宽度，如果加上当前字符的宽度会超过 100，就将 lines 加 1，并将 current_width 重置为当前字符的宽度；否则将当前字符的宽度加到 current_width 上。最后返回 [lines, current_width]，表示需要的行数和最后一行使用的宽度。

时间复杂度: O(n)

空间复杂度: O(1)

from typing import List

class Solution:
    def numberOfLines(self, widths: List[int], s: str) -> List[int]:
        lines = 1  # 需要的行数，初始为1
        current_width = 0  # 当前行已使用的宽度
        
        for char in s:
            char_width = widths[ord(char) - ord('a')]  # 计算当前字符需要的宽度
            if current_width + char_width > 100:  # 如果加上当前字符宽度会超过100
                lines += 1  # 需要的行数加1
                current_width = char_width  # 重置当前行已使用宽度为当前字符宽度
            else:
                current_width += char_width  # 否则将当前字符宽度加到当前行已使用宽度上
        
        return [lines, current_width]  # 返回需要的行数和最后一行使用的宽度

Explore

根据算法的逻辑，如果添加当前字符后，当前行宽度正好等于100个单位，那么这个字符可以继续在当前行写入，不需要另起一行。算法中的条件是检查新的宽度是否会超过100（current_width + char_width > 100），所以如果正好等于100，不会触发新行的条件。

算法在处理空字符串`S`时，由于不会进入for循环（没有字符去增加宽度），因此`lines`保持为初始值1，`current_width`保持为0。所以，算法会返回[1, 0]，表示需要一行，但这行没有使用任何宽度。

确实如此，`lines`变量是初始设置为1，意味着算法默认至少需要一行，即使字符串`S`为空。这种设计可能是为了统一返回格式，保证总是至少有一行，即使没有任何字符输出。

如果`widths`数组中存在超过100的宽度值，算法在当前实现下会直接在新行开始这个字符，即使其宽度超过了100个单位。算法没有特别处理单个字符宽度超出100单位的情况。在实际应用中，可能需要修改算法或前置条件，确保所有字符宽度都不超过100单位，或者调整算法以处理这种异常情况。