Рубрики

Количество строк, необходимых для записи данной строки

Дана строка str и целочисленный массив width [] где:

width[0] = width of character ‘a’
width[1] = width of character ‘b’

width[25] = width of character ‘z’

Задача состоит в том, чтобы найти количество строк, которое потребуется для записи строки str на бумаге, и ширину последней строки, до которой она занята.
Примечание: ширина линии составляет 10 единиц .

Примеры:

Input: str = “bbbcccdddaa”,
width[] = {4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
Output: (2, 8)
“bbbcccddd” will cover first line (9 * 1 = 9 units)
As ‘a’ has a width of 4 which cannot fit the remaining 1 unit in the first line.
It’ll have to be written in the second line.
So, next line will contain “aa” covering 4 * 2 = 8 units.
We need 1 full line and one line with width 8 units.

Input: str = “abcdefghijklmnopqrstuvwxyz”,
width[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
Output: (3, 6)
All the characters have the same width of 1. To write all 26 characters,
We need 2 full lines and one line with width 6 units.

Подход: мы будем записывать каждый символ в строке str один за другим. Когда мы пишем символ, мы немедленно обновляем (линии, ширина), который отслеживает, сколько строк мы использовали до сих пор и какова длина используемого пространства в последней строке.
Если ширина [char] в str соответствует нашей текущей строке, мы добавим ее. В противном случае мы начнем с новой строки

Ниже приведена реализация вышеуказанного подхода:

python3

# Python3 реализация подхода

  
# Функция для возврата необходимого количества строк

def numberOfLines(S, widths):

  

    # Если строка пуста

    if(S == ""):

        return 0, 0

  

    # Инициализировать линии и ширину

    lines, width = 1, 0

  

    # Итерировать через S

    for c in S:

        w = widths[ord(c) - ord('a')]

        width += w

        if width > 10:

            lines += 1

            width = w

  

    # Вернуть строки и ширину

    return lines, width

  

  
Код водителя

S = "bbbcccdddaa"

Widths = [4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,

 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

  
# Вызов функции для печати требуемого ответа

print(numberOfLines(S, Widths))

Выход:

(2, 8)

Рекомендуемые посты:

Количество строк, необходимых для записи данной строки

0.00 (0%) 0 votes