Easy

题目描述

给你一个字符串 s，由小写英文字母组成，以及一个数组 widths 表示每个小写英文字母的像素宽度。具体地，widths[0] 是字母 'a' 的宽度，widths[1] 是字母 'b' 的宽度，以此类推。

你需要把字符串 s 写在若干行上，每行的宽度不能超过 100 像素。从字符串的开始处开始，在第一行上写尽可能多的字母，使得总宽度不超过 100 像素。然后，从 s 中停下的地方继续，在第二行上写尽可能多的字母。继续这个过程，直到你写完所有的 s。

返回一个长度为 2 的数组 result，其中：

  • result[0] 是总的行数。
  • result[1] 是最后一行的宽度（以像素为单位）。

示例 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]
解释：你可以这样写 s：
abcdefghij  // 100 像素宽
klmnopqrst  // 100 像素宽
uvwxyz      // 60 像素宽
总共有 3 行，最后一行宽度为 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]
解释：你可以这样写 s：
bbbcccdddaa  // 98 像素宽
a            // 4 像素宽
总共有 2 行，最后一行宽度为 4 像素。

提示：

  • widths.length == 26
  • 2 <= widths[i] <= 10
  • 1 <= s.length <= 1000
  • s 只包含小写英文字母。

解题思路

这是一道模拟题，需要模拟写字符串的过程。

解题思路：

题目要求我们将字符串 s 分行写，每行最多 100 像素宽度。我们需要统计总行数和最后一行的宽度。

基本思路是贪心算法：

  1. 从左到右遍历字符串中的每个字符
  2. 对于每个字符，获取其对应的像素宽度（通过 widths 数组）
  3. 如果当前行加上这个字符的宽度不超过 100，就将字符添加到当前行
  4. 如果超过 100，就开始新的一行，将当前字符作为新行的第一个字符
  5. 记录总行数和最后一行的宽度

算法步骤：

  1. 初始化行数为 1，当前行宽度为 0
  2. 遍历字符串中的每个字符：
    • 计算字符的宽度：widths[c - 'a']
    • 如果当前行宽度 + 字符宽度 ≤ 100，累加到当前行宽度
    • 否则，行数加 1，当前行宽度重置为该字符的宽度
  3. 返回 [行数, 最后一行宽度]

这种方法时间复杂度为 O(n)，空间复杂度为 O(1)，是最优解法。

代码实现

class Solution {
public:
    vector<int> numberOfLines(vector<int>& widths, string s) {
        int lines = 1;
        int currentWidth = 0;
        
        for (char c : s) {
            int charWidth = widths[c - 'a'];
            if (currentWidth + charWidth > 100) {
                lines++;
                currentWidth = charWidth;
            } else {
                currentWidth += charWidth;
            }
        }
        
        return {lines, currentWidth};
    }
};

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

public class Solution {
    public int[] NumberOfLines(int[] widths, string s) {
        int lines = 1;
        int currentWidth = 0;
        
        foreach (char c in s) {
            int charWidth = widths[c - 'a'];
            if (currentWidth + charWidth > 100) {
                lines++;
                currentWidth = charWidth;
            } else {
                currentWidth += charWidth;
            }
        }
        
        return new int[] {lines, currentWidth};
    }
}

var numberOfLines = function(widths, s) {
    let lines = 1;
    let currentWidth = 0;
    
    for (let c of s) {
        let charWidth = widths[c.charCodeAt(0) - 'a'.charCodeAt(0)];
        if (currentWidth + charWidth > 100) {
            lines++;
            currentWidth = charWidth;
        } else {
            currentWidth += charWidth;
        }
    }
    
    return [lines, currentWidth];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)其中 n 是字符串 s 的长度，需要遍历每个字符一次
空间复杂度O(1)只使用了常数个变量存储行数和当前宽度