Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/806.html
806. Number of Lines To Write String (Easy)
We are to write the letters of a given string S
, from left to right into lines. Each line has maximum width 100 units, and if writing a letter would cause the width of the line to exceed 100 units, it is written on the next line. We are given an array widths
, an array where widths[0] is the width of 'a', widths[1] is the width of 'b', ..., and widths[25] is the width of 'z'.
Now answer two questions: how many lines have at least one character from S
, and what is the width used by the last such line? Return your answer as an integer list of length 2.
Example : 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,10] S = "abcdefghijklmnopqrstuvwxyz" Output: [3, 60] Explanation: All letters have the same length of 10. To write all 26 letters, we need two full lines and one line with 60 units.
Example : Input: 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" Output: [2, 4] Explanation: All letters except 'a' have the same length of 10, and "bbbcccdddaa" will cover 9 * 10 + 2 * 4 = 98 units. For the last 'a', it is written on the second line because there is only 2 units left in the first line. So the answer is 2 lines, plus 4 units in the second line.
Note:
- The length of
S
will be in the range [1, 1000]. S
will only contain lowercase letters.widths
is an array of length26
.widths[i]
will be in the range of[2, 10]
.
Solution 1.
-
class Solution { public int[] numberOfLines(int[] widths, String S) { final int MAX_WIDTH = 100; int linesCount = 1, curWidth = 0; int length = S.length(); for (int i = 0; i < length; i++) { char c = S.charAt(i); int width = widths[c - 'a']; if (curWidth + width <= MAX_WIDTH) curWidth += width; else { linesCount++; curWidth = width; } } return new int[]{linesCount, curWidth}; } } ############ class Solution { private static final int MAX_WIDTH = 100; public int[] numberOfLines(int[] widths, String s) { int last = 0, row = 1; for (char c : s.toCharArray()) { int w = widths[c - 'a']; if (last + w <= MAX_WIDTH) { last += w; } else { ++row; last = w; } } return new int[] {row, last}; } }
-
// OJ: https://leetcode.com/problems/number-of-lines-to-write-string/ // Time: O(N) // Space: O(1) class Solution { public: vector<int> numberOfLines(vector<int>& widths, string S) { int lineWidth = 0, cnt = 1; for (char c : S) { if (lineWidth + widths[c - 'a'] > 100) { lineWidth = 0; ++cnt; } lineWidth += widths[c - 'a']; } return { cnt, lineWidth }; } };
-
class Solution: def numberOfLines(self, widths: List[int], s: str) -> List[int]: last, row = 0, 1 for c in s: w = widths[ord(c) - ord('a')] if last + w <= 100: last += w else: row += 1 last = w return [row, last] ############ class Solution(object): def numberOfLines(self, widths, S): """ :type widths: List[int] :type S: str :rtype: List[int] """ lines = 1 last = 0 for s in S: width = widths[ord(s) - ord('a')] last += width if last > 100: lines += 1 last = width return [lines, last]
-
func numberOfLines(widths []int, s string) []int { last, row := 0, 1 for _, c := range s { w := widths[c-'a'] if last+w <= 100 { last += w } else { row++ last = w } } return []int{row, last} }
-
impl Solution { pub fn number_of_lines(widths: Vec<i32>, s: String) -> Vec<i32> { let mut count = 1; let mut sum = 0; for c in s.as_bytes() { let width = widths[(c - b'a') as usize]; if sum + width > 100 { sum = 0; count += 1; } sum += width; } vec![count, sum] } }