LeetCode 68. 文本左右对齐

Categories:

题目描述
思路分析
1. 解法一：贪心逐行构造（推荐）
相似题目

题目描述

✅ 68. 文本左右对齐

思路分析

解法一：贪心逐行构造（推荐）

核心思路：

从左到右尽量多放单词，直到无法放入下一词。

若为最后一行或仅一个单词：左对齐，单词间一个空格，末尾补空格。

否则均匀分配空格，多余空格放左侧。

复杂度分析：

时间复杂度：O(n)，其中 n 表示单词总数。

空间复杂度：O(1)（不计输出）。

// 贪心构造每一行
class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> res = new ArrayList<>();
        int i = 0;

        while (i < words.length) {
            int len = words[i].length();
            int j = i + 1;
            while (j < words.length && len + 1 + words[j].length() <= maxWidth) {
                len += 1 + words[j].length();
                j++;
            }

            int wordCount = j - i;
            int totalChars = 0;
            for (int k = i; k < j; k++) {
                totalChars += words[k].length();
            }

            StringBuilder sb = new StringBuilder();
            if (j == words.length || wordCount == 1) {
                for (int k = i; k < j; k++) {
                    if (k > i) {
                        sb.append(' ');
                    }
                    sb.append(words[k]);
                }
                while (sb.length() < maxWidth) {
                    sb.append(' ');
                }
            } else {
                int spaces = maxWidth - totalChars;
                int gap = spaces / (wordCount - 1);
                int extra = spaces % (wordCount - 1);
                for (int k = i; k < j; k++) {
                    if (k > i) {
                        int count = gap + (extra > 0 ? 1 : 0);
                        extra--;
                        for (int s = 0; s < count; s++) {
                            sb.append(' ');
                        }
                    }
                    sb.append(words[k]);
                }
            }

            res.add(sb.toString());
            i = j;
        }

        return res;
    }
}

// 贪心构造每一行
func fullJustify(words []string, maxWidth int) []string {
	res := make([]string, 0)
	i := 0

	for i < len(words) {
		length := len(words[i])
		j := i + 1
		for j < len(words) && length+1+len(words[j]) <= maxWidth {
			length += 1 + len(words[j])
			j++
		}

		wordCount := j - i
		totalChars := 0
		for k := i; k < j; k++ {
			totalChars += len(words[k])
		}

		var sb []byte
		if j == len(words) || wordCount == 1 {
			for k := i; k < j; k++ {
				if k > i {
					sb = append(sb, ' ')
				}
				sb = append(sb, words[k]...)
			}
			for len(sb) < maxWidth {
				sb = append(sb, ' ')
			}
		} else {
			spaces := maxWidth - totalChars
			gap := spaces / (wordCount - 1)
			extra := spaces % (wordCount - 1)
			for k := i; k < j; k++ {
				if k > i {
					count := gap
					if extra > 0 {
						count++
						extra--
					}
					for s := 0; s < count; s++ {
						sb = append(sb, ' ')
					}
				}
				sb = append(sb, words[k]...)
			}
		}

		res = append(res, string(sb))
		i = j
	}

	return res
}

相似题目

题目	难度	考察点
14. 最长公共前缀	简单	字符串
151. 反转字符串中的单词	中等	字符串
415. 字符串相加	简单	字符串
6. Z 字形变换	中等	字符串
43. 字符串相乘	中等	字符串

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/37423583