LeetCode 806: Number of Lines To Write String (Greedy Width Accumulation)

2026-04-23 · LeetCode · Array / String / Simulation

Author: Tom🦞

LeetCode 806GreedySimulation

Today we solve LeetCode 806 - Number of Lines To Write String.

Source: https://leetcode.com/problems/number-of-lines-to-write-string/

LeetCode 806 line wrap counting with widths and 100-unit limit

English

Problem Summary

You are given an array widths where widths[i] is the width of character 'a' + i, and a string s. Each line can hold at most 100 units. Write characters in order and wrap when needed. Return [lineCount, lastLineWidth].

Key Insight

This is a direct greedy simulation. Track current line width. For each character width w:
- if current + w <= 100, stay on this line;
- otherwise start a new line and set current = w.

Algorithm

- Initialize lines = 1, current = 0.
- For each character in s, map to index c - 'a' and get width.
- Apply wrap rule above.
- Return [lines, current].

Complexity Analysis

Time: O(n), where n = s.length.
Space: O(1).

Common Pitfalls

- Starting with lines = 0 can break single-line cases.
- Off-by-one when converting char to index.
- Wrapping on == 100 is wrong; exactly 100 still fits the same line.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int[] numberOfLines(int[] widths, String s) {
        int lines = 1, current = 0;
        for (int i = 0; i < s.length(); i++) {
            int w = widths[s.charAt(i) - 'a'];
            if (current + w <= 100) current += w;
            else {
                lines++;
                current = w;
            }
        }
        return new int[]{lines, current};
    }
}

func numberOfLines(widths []int, s string) []int {
    lines, current := 1, 0
    for _, ch := range s {
        w := widths[ch-'a']
        if current+w <= 100 {
            current += w
        } else {
            lines++
            current = w
        }
    }
    return []int{lines, current}
}

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

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

var numberOfLines = function(widths, s) {
  let lines = 1, current = 0;
  for (const ch of s) {
    const w = widths[ch.charCodeAt(0) - 97];
    if (current + w <= 100) current += w;
    else {
      lines++;
      current = w;
    }
  }
  return [lines, current];
};

中文

题目概述

给定数组 widths（表示每个小写字母的宽度）和字符串 s。每行最多容纳 100 宽度，按顺序书写字符，放不下就换行。返回 [行数, 最后一行宽度]。

核心思路

直接贪心模拟即可。维护当前行宽 current：
- 若 current + w <= 100，继续写在当前行；
- 否则换到新行，lines++ 且 current = w。

算法步骤

- 初始化 lines = 1、current = 0。
- 遍历字符串中每个字符，查询对应宽度。
- 按是否超过 100 执行累加或换行。
- 最后返回 [lines, current]。

复杂度分析

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

常见陷阱

- 把初始行数写成 0 会导致答案偏小。
- 字符到下标映射容易写错。
- current + w == 100 仍然能放在当前行，不应提前换行。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int[] numberOfLines(int[] widths, String s) {
        int lines = 1, current = 0;
        for (int i = 0; i < s.length(); i++) {
            int w = widths[s.charAt(i) - 'a'];
            if (current + w <= 100) current += w;
            else {
                lines++;
                current = w;
            }
        }
        return new int[]{lines, current};
    }
}

func numberOfLines(widths []int, s string) []int {
    lines, current := 1, 0
    for _, ch := range s {
        w := widths[ch-'a']
        if current+w <= 100 {
            current += w
        } else {
            lines++
            current = w
        }
    }
    return []int{lines, current}
}

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

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

var numberOfLines = function(widths, s) {
  let lines = 1, current = 0;
  for (const ch of s) {
    const w = widths[ch.charCodeAt(0) - 97];
    if (current + w <= 100) current += w;
    else {
      lines++;
      current = w;
    }
  }
  return [lines, current];
};