C/C++ | LeetCode

Задача: 68. Text Justification
Сложность: hard

Дан массив слов words и ширина строки maxWidth. Необходимо вернуть текст, в котором строки выровнены по ширине с равномерным распределением пробелов, кроме последней строки — она выравнивается по левому краю.

Пример:

Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
Output:
arduino[
   "This    is    an",
   "example  of text",
   "justification.  "
]

👨‍💻 Алгоритм:

1⃣Разделить слова на строки: жадно добавлять слова, пока их суммарная длина + пробелы не превышают maxWidth

2⃣Создать строку с выравниванием:
если последняя строка или в строке одно слово — выравниваем по левому краю
иначе: равномерно распределяем пробелы между словами, остаток пробелов добавляется слева

3⃣Склеить строки и вернуть результат

😎 Решение:

class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> ans;
        int i = 0;
        while (i < words.size()) {
            vector<string> currentLine = getWords(i, words, maxWidth);
            i += currentLine.size();
            ans.push_back(createLine(currentLine, i, words, maxWidth));
        }
        return ans;
    }

private:
    vector<string> getWords(int i, vector<string>& words, int maxWidth) {
        vector<string> currentLine;
        int currLength = 0;
        while (i < words.size() && currLength + words[i].size() <= maxWidth) {
            currentLine.push_back(words[i]);
            currLength += words[i].size() + 1;
            i++;
        }
        return currentLine;
    }

    string createLine(vector<string>& line, int i, vector<string>& words, int maxWidth) {
        int baseLength = -1;
        for (const string& word : line) {
            baseLength += word.size() + 1;
        }
        int extraSpaces = maxWidth - baseLength;

        // Последняя строка или строка с одним словом
        if (line.size() == 1 || i == words.size()) {
            string res = join(line, " ");
            res += string(extraSpaces, ' ');
            return res;
        }

        int wordCount = line.size() - 1;
        int spacesPerWord = extraSpaces / wordCount;
        int needsExtraSpace = extraSpaces % wordCount;

        for (int j = 0; j < needsExtraSpace; j++) {
            line[j] += " ";
        }
        for (int j = 0; j < wordCount; j++) {
            line[j] += string(spacesPerWord, ' ');
        }

        return join(line, " ");
    }

    string join(vector<string>& line, const string& delimeter) {
        if (line.empty()) return "";
        string res = line[0];
        for (int i = 1; i < line.size(); i++) {
            res += delimeter + line[i];
        }
        return res;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Please open Telegram to view this post