TikTok 段落排版：贪心换行与左右补空格

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练宽度 W>0，用 code point 长度计；每词非空且不含空白，每词长度≤W。
• 词之间单空格，每行左/右对齐补至恰好 W；超长词拒绝，不猜拆分方式。空段落输出空列表。

解题路线

1. 维护当前词列表和含词间空格的长度。加入新词需要 len(word)+(当前非空?1:0)，超过 W 时先输出当前行，再用该词开新行。
2. 贪心理由：词序固定，当前行放最长可行前缀，不会减少后续可用空间；它实现题目指定的持续加入直至超宽规则，不是最小 raggedness 排版。
3. 左对齐尾部补空格，右对齐头部补空格；不在词间分配额外空格，否则变成两端对齐。
4. 段落边界独立换行，各段选择自己的 alignment。显示列宽涉及汉字、emoji 和终端字体，不能直接用 len 替代。

手动走一遍

W=6，词["aa","bbb","c"]先放 "aa bbb"，再 "c"。右对齐第二行变成五空格加c。W=3、词abcd按本文合同拒绝；若允许拆词，要补充拆分及连字符规则。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def wrap_paragraph(words, width, alignment):
    """Words are nonempty, contain no whitespace, and each fits the width.
    Every output line has exactly width code points; empty paragraph -> []."""
    if width < 1 or alignment not in ('left', 'right'):
        raise ValueError('positive width and left/right alignment required')
    if any(not word or any(c.isspace() for c in word) or len(word) > width for word in words):
        raise ValueError('invalid or oversized word')
    result, line, length = [], [], 0
    def emit():
        value = ' '.join(line)
        result.append(value.ljust(width) if alignment == 'left' else value.rjust(width))
    for word in words:
        needed = len(word) + bool(line)
        if length + needed > width:
            emit()
            line, length = [], 0
        length += len(word) + bool(line)
        line.append(word)
    if line:
        emit()
    return result

复杂度

输入总字符 C、输出含补白总字符 L，O(C+L) 时间；当前行空间≤O(W)，存全部结果 O(L)。

易错点与追问

容易失分的边界

• 漏算单词间空格。
• 超长词触发空行或死循环。
• 左右对齐误成两端对齐。

继续深挖

• 宽度按显示列如何实现？
• 如果要优化整段参差度为什么需要 DP？