68. Text Justificator

Text Justification

对Queue有初步体验的好题目

给定一堆字 要求尽可能把本来相邻的字放在同一句

但是每句的长度非得刚好凑到maxWidth

然后每句中的 字之间必须有空格

具体空格要放多少 取决于场景

先进先出

首先安排个队列 装那些 正在集结一起成句 的字

由于相邻两字之间起码有个空格 因此队列中这些字

会形成的句子长度 起码是 $L = len(queue) - 1 + \Sigma_i \; len(word_i)$

可能性1：长度超标

一旦目前迭代到的字$word_j$ 造成了

$L + 1 + len(word_j) >$maxWidth

那么这就是队列已经要全数成句子的时机

它们成句子后 自然清空队列 让$word_j$进队列 打响下一句的第一炮

可能性2：空间还够

否则的话 就是单纯$word_j$进队列 句子尚未非得成形 还能再等

确定要成形的句子

前面有说 句子成形时 相邻俩字中间空格怎么填 要看场景

题目的规定是两种不同风格的填空机制

1. Left Justification

如果成形的句子是最后一句 那么就要左对齐

也就是说 相邻俩字中间刚好塞一个空格

要是填完发现长度还没摸到maxWidth

直接在句子末尾补空格灌水啰

由此可见 不是最后一句的句子 倘若仅带著一个字

那这时该句的空格操作 事实上自动变为左对齐

2. Right Justification

不是最后一句且夹带起码两字 的句子采取右对齐

先看有$len(queue) - 1$这么多个字与字之间缝隙

总共得填充$S =$maxWidth $- \Sigma_i \; len(word_i)$这么多空格

于是每个缝隙先各自填

$\lfloor S // (len(queue) - 1) \rfloor$这么多空格

当然通常馀数$M = S \bmod{(len(queue) - 1)}$是大于零的

换言之还要安排最后这$M$个空格 才能凑齐句长maxWidth

这也非常简单 抓最左边的$M$个缝隙

叫它们来各自额外多收个空格即可

左右对齐都掌握好了 此题自然到手

C++

#include <deque>
#include <string>
#include <vector>
using namespace std;

class TextJustificator // LeetCode Q.68.
{
private:
    deque<string> queue;

    string formSentence(int charsCount, int maxWidth, bool leftJustify) {
        string intervalSpaces = "";
        int intervalsCount = queue.size() - 1, modulo = 0;

        if (intervalsCount > 0 && !leftJustify) {
            int quotient = (maxWidth - charsCount) / intervalsCount;
            for (int num = 0; num < quotient; num++)
                intervalSpaces += " ";

            modulo = (maxWidth - charsCount) % intervalsCount;
        }

        string sentence = "";

        for (int idx = 0; idx < queue.size(); idx++) {
            sentence += queue[idx];

            if (idx < queue.size() - 1) // Not the last word.
            {
                if (leftJustify) {
                    sentence += " "; // Left-justification.
                    continue;
                }

                sentence += intervalSpaces; // Right-justification.
                if (modulo > idx)
                    sentence += " "; // Need to pad extra space at left intervals.
            }
        }
        queue.clear(); // Reset for future usage.

        // Right end padding only runs for left-justification.
        while (sentence.size() < maxWidth)
            sentence += " ";
        return sentence;
    }

public:
    vector<string> justifyText(vector<string>& words, int maxWidth) {
        vector<string> justifiedSentences;
        int charsCount = 0; // Characters only. Not counting interval spaces.

        for (const auto& word : words) {
            // Current sentence is finalized.
            if (charsCount + queue.size() - 1 + word.size() + 1 > maxWidth) {
                string sentence = formSentence(charsCount, maxWidth, false);
                justifiedSentences.push_back(sentence);
                charsCount -= charsCount; // Reset for the next sentence.
            }

            queue.push_back(word);
            charsCount += word.size();
        }

        // Deal with last sentence. Last sentence must be left-justified.
        string sentence = formSentence(charsCount, maxWidth, true);
        justifiedSentences.push_back(sentence);
        return justifiedSentences;
    }
};

Python

class TextJustificator:  # LeetCode Q.68.
    def __init__(self) -> None:
        self.queue: list[str] = []

    def _form_sentence(self, chars_count: int, max_width: int, left_justify: bool) -> str:
        interval_spaces = ""
        intervals_count = len(self.queue) - 1
        modulo = 0

        if intervals_count > 0 and not left_justify:
            quotient = (max_width - chars_count) // intervals_count
            interval_spaces += " " * quotient

            modulo = (max_width - chars_count) % intervals_count

        sentence = ""

        for idx, word in enumerate(self.queue):
            sentence += word

            if idx < len(self.queue) - 1:  # Not the last word.
                if left_justify:
                    sentence += " "  # Left-justification.
                    continue

                sentence += interval_spaces  # Right-justification.
                if modulo > idx:
                    sentence += " "  # Need to pad extra space at left intervals.

        self.queue.clear()  # Reset for future usage.

        # Right end padding only runs for left-justification.
        return sentence + " " * (max_width - len(sentence))

    def justify_text(self, words: list[str], max_width: int) -> list[str]:
        self.queue = []

        justified_sentences: list[str] = []
        chars_count = 0  # Characters only. Not counting interval spaces.

        for word in words:
            # Current sentence is finalized.
            if chars_count + len(self.queue) - 1 + len(word) + 1 > max_width:
                sentence = self._form_sentence(chars_count, max_width, False)
                justified_sentences.append(sentence)
                chars_count -= chars_count  # Reset for the next sentence.

            self.queue.append(word)
            chars_count += len(word)

        # Deal with last sentence. Last sentence must be left-justified.
        sentence = self._form_sentence(chars_count, max_width, True)
        justified_sentences.append(sentence)
        return justified_sentences

时间和空间复杂度都是$O(n)$