Make writing a habit together! This is the 12th day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

Topic describes

This is 806 on LeetCode. The number of lines needed to write a string. Difficulty is easy.

Tag: “Simulation”

We write the given string S from left to right on each line. Each line has a maximum width of 100,100,100 units. If we write a letter and the line exceeds 100,100,100 units, we should write the letter on the next line.

We given the widths of an array, the array widths [0] widths [0] widths [0] units on behalf of the ‘a’ need, widths [1] widths [1] widths [1] on behalf of the ‘b’ need unit,… , widths[25] Widths [25] Widths [25] represents the units needed for ‘z’.

Now answer two questions: How many lines should fit the S, and how many units of width should the last line use?

Return your answers as a list of integers of length 222.

Example 1:

Input: S =,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 widths = [10] "Abcdefghijklmnopqrstuvwxyz" output: [60] 3, explanation: all characters have the same unit 10. So to write all 26 letters, we need 2 full lines and a line that takes up 60 units.Copy the code

Example 2:

Input: 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 [4] = "bbbcccdddaaa" S output: [2, 4] Explanation: All characters except the letter 'a' are the same unit 10, and the string "bbbccCDDDAa" will cover 9 * 10 + 2 * 4 = 98 units. The last letter 'A' will be written to the second line, because there are only 2 units left on the first line. So, this answer is 2 rows, and the second row is 4 units wide.Copy the code

Note:

  • stringSThe length of the
    [ 1 . 1000 ] [1, 1000]     The scope of.
  • SContains only lowercase letters.
  • widthsIs the length of
    26 26     The array.
  • Widths [I] Widths [I] Widths [I]widths[I] values range from [2,10][2, 10][2,10].

simulation

Carry out the simulation according to the meaning of the question.

Use the variable A to indicate how many rows are currently full, and use the variable B to indicate where the fill cursor is currently located.

Code:

class Solution {
    public int[] numberOfLines(int[] widths, String s) {
        int a = 0, b = 0;
        for (char c : s.toCharArray()) {
            int t = widths[c - 'a'];
            if (b + t > 100 && ++a >= 0) b = t;
            else b += t;         
        }
        if(b ! =0) a++;
        return new int[]{a, b}; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: Not usedtoCharArray 为
    O ( 1 ) O(1)     , or for
    O ( n ) O(n)

The last

This is the No.804 of our “Brush through LeetCode” series. The series started on 2021/01/01.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.