Сложность: hard
Дан массив строк words и ширина maxWidth. Необходимо отформатировать текст таким образом, чтобы каждая строка содержала ровно maxWidth символов и была полностью (слева и справа) выровнена.
Слова следует упаковывать жадным способом; то есть стараться поместить как можно больше слов в каждую строку. Дополнительные пробелы ' ' следует добавлять по мере необходимости, чтобы каждая строка имела ровно maxWidth символов.
Дополнительные пробелы между словами должны распределяться как можно более равномерно. Если количество пробелов в строке не делится поровну между словами, то пустые места слева будут содержать больше пробелов, чем места справа.
Для последней строки текста выравнивание должно быть по левому краю, и между словами не добавляются дополнительные пробелы.
Примечание:
Слово определяется как последовательность символов, не содержащих пробелы.
Длина каждого слова гарантированно больше 0 и не превышает maxWidth.
Входной массив words содержит хотя бы одно слово.
Пример:
Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
Output:
[
"This is an",
"example of text",
"justification. "
]
👨💻 Алгоритм:
1️⃣Создайте два вспомогательных метода getWords и createLine, описанные выше.
2️⃣Инициализируйте список ответов ans и целочисленную переменную i для итерации по входным данным. Используйте цикл while для перебора входных данных. Каждая итерация в цикле while будет обрабатывать одну строку в ответе.
3️⃣Пока i < words.length, выполните следующие шаги:
Получите слова, которые должны быть в текущей строке, как currentLine = getWords(i).
Увеличьте i на currentLine.length.
Создайте строку, вызвав createLine(line, i), и добавьте её в ans.
Верните ans.
😎 Решение:
class Solution:
def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
def get_words(i):
current_line = []
curr_length = 0
while i < len(words) and curr_length + len(words[i]) <= maxWidth:
current_line.append(words[i])
curr_length += len(words[i]) + 1
i += 1
return current_line
def create_line(line, i):
base_length = -1
for word in line:
base_length += len(word) + 1
extra_spaces = maxWidth - base_length
if len(line) == 1 or i == len(words):
return " ".join(line) + " " * extra_spaces
word_count = len(line) - 1
spaces_per_word = extra_spaces // word_count
needs_extra_space = extra_spaces % word_count
for j in range(needs_extra_space):
line[j] += " "
for j in range(word_count):
line[j] += " " * spaces_per_word
return " ".join(line)
ans = []
i = 0
while i < len(words):
current_line = get_words(i)
i += len(current_line)
ans.append(create_line(current_line, i))
return ans
Ставь 👍 и забирай 📚 Базу знаний