Given a list of words and a maximum line length, format the text so each line is exactly that length. Rules:
Greedy packing: pack as many words as possible onto each line (separated by at least one space).
Extra spaces in multi-word lines: distribute extra spaces evenly between words; if they don't divide evenly, the leftmost gaps get one extra each. Output uses _ instead of space.
Single-word lines: center the word (pad // 2 underscores on the left, the rest on the right). If pad is odd, the extra goes to the right.
Hyphenated words: words like "self-inflicted", "pre-approval", "mother-in-law" should be kept on one line if possible. If only the prefix-with-hyphen fits (e.g. "self-"), split the word across lines. Inputs may have whitespace around hyphens ("self - inflicted"); normalize them as if there were no whitespace.
Example
words = "auto-complete is my go - to", lineLength = 8
→ ["_auto-__", "complete", "is____my", "_go-to__"]
words = "cat is an animal and so is a dog", lineLength = 12
→ ["cat__is__an_", "animal__and_", "so_is_a_dog_"]
words = "human", lineLength = 8
→ "_human__"Constraints
1 ≤ lineLength ≤ 100, total word characters fit within reasonable memory.
解法
规范化连字符两侧空白，贪心装行。若带连字符的词放不下，拆出最长能放下的「前缀-」。用 _ 填充：单词行居中(左侧 = pad/2)，多词行把多余空格均匀分到各间隙，剩余从左开始多分。复杂度 O(N)。
import re
def justify(text, L):
text = re.sub(r'\s*-\s*', '-', text)
words = text.split()
lines = []
cur, cur_len = [], 0
i = 0
while i < len(words):
w = words[i]
need = len(w) + (1 if cur else 0)
if cur_len + need <= L:
cur.append(w)
cur_len += need
i += 1
continue
split = False
if '-' in w:
parts = w.split('-')
best_prefix = ''
best_k = -1
for k in range(len(parts) - 1):
cand = '-'.join(parts[:k+1]) + '-'
ext = len(cand) + (1 if cur else 0)
if cur_len + ext <= L:
best_prefix, best_k = cand, k
if best_prefix:
cur.append(best_prefix)
words[i] = '-'.join(parts[best_k+1:])
split = True
lines.append(cur)
cur, cur_len = [], 0
if cur:
lines.append(cur)
out = []
for line in lines:
word_len = sum(len(w) for w in line)
pad = L - word_len
if len(line) == 1:
left = pad // 2
out.append('_' * left + line[0] + '_' * (pad - left))
else:
gaps = len(line) - 1
base, extra = divmod(pad, gaps)
s = ''
for j, w in enumerate(line):
s += w
if j < gaps:
s += '_' * (base + (1 if j < extra else 0))
out.append(s)
return outclass Solution {
public List<String> justify(String text, int L) {
text = text.replaceAll("\\s*-\\s*", "-");
List<String> words = new ArrayList<>(Arrays.asList(text.trim().split("\\s+")));
List<List<String>> lines = new ArrayList<>();
List<String> cur = new ArrayList<>();
int curLen = 0, i = 0;
while (i < words.size()) {
String w = words.get(i);
int need = w.length() + (cur.isEmpty() ? 0 : 1);
if (curLen + need <= L) {
cur.add(w); curLen += need; i++; continue;
}
if (w.contains("-")) {
String[] parts = w.split("-");
String bestPrefix = "";
int bestK = -1;
StringBuilder sb = new StringBuilder();
for (int k = 0; k < parts.length - 1; k++) {
if (k > 0) sb.append('-');
sb.append(parts[k]);
String cand = sb.toString() + "-";
int ext = cand.length() + (cur.isEmpty() ? 0 : 1);
if (curLen + ext <= L) { bestPrefix = cand; bestK = k; }
}
if (!bestPrefix.isEmpty()) {
cur.add(bestPrefix);
StringBuilder rem = new StringBuilder();
for (int k = bestK + 1; k < parts.length; k++) {
if (k > bestK + 1) rem.append('-');
rem.append(parts[k]);
}
words.set(i, rem.toString());
}
}
lines.add(new ArrayList<>(cur));
cur.clear(); curLen = 0;
}
if (!cur.isEmpty()) lines.add(cur);
List<String> out = new ArrayList<>();
for (List<String> line : lines) {
int wordLen = 0;
for (String w : line) wordLen += w.length();
int pad = L - wordLen;
StringBuilder s = new StringBuilder();
if (line.size() == 1) {
int left = pad / 2;
for (int k = 0; k < left; k++) s.append('_');
s.append(line.get(0));
for (int k = 0; k < pad - left; k++) s.append('_');
} else {
int gaps = line.size() - 1;
int base = pad / gaps, extra = pad % gaps;
for (int j = 0; j < line.size(); j++) {
s.append(line.get(j));
if (j < gaps) {
int sp = base + (j < extra ? 1 : 0);
for (int k = 0; k < sp; k++) s.append('_');
}
}
}
out.add(s.toString());
}
return out;
}
}#include <regex>
vector<string> justify(string text, int L) {
text = regex_replace(text, regex("\\s*-\\s*"), "-");
vector<string> words;
stringstream ss(text);
string token;
while (ss >> token) words.push_back(token);
vector<vector<string>> lines;
vector<string> cur;
int curLen = 0;
size_t i = 0;
while (i < words.size()) {
string w = words[i];
int need = w.size() + (cur.empty() ? 0 : 1);
if (curLen + need <= L) {
cur.push_back(w);
curLen += need;
i++;
continue;
}
if (w.find('-') != string::npos) {
vector<string> parts;
size_t l = 0;
while (l <= w.size()) {
size_t r = w.find('-', l);
parts.push_back(w.substr(l, r == string::npos ? string::npos : r - l));
if (r == string::npos) break;
l = r + 1;
}
string bestPrefix;
int bestK = -1;
string acc;
for (size_t k = 0; k + 1 < parts.size(); k++) {
if (k > 0) acc += '-';
acc += parts[k];
string cand = acc + "-";
int ext = cand.size() + (cur.empty() ? 0 : 1);
if (curLen + ext <= L) { bestPrefix = cand; bestK = k; }
}
if (!bestPrefix.empty()) {
cur.push_back(bestPrefix);
string rem;
for (size_t k = bestK + 1; k < parts.size(); k++) {
if (k > (size_t)bestK + 1) rem += '-';
rem += parts[k];
}
words[i] = rem;
}
}
lines.push_back(cur);
cur.clear();
curLen = 0;
}
if (!cur.empty()) lines.push_back(cur);
vector<string> out;
for (auto& line : lines) {
int wordLen = 0;
for (auto& w : line) wordLen += w.size();
int pad = L - wordLen;
string s;
if (line.size() == 1) {
int left = pad / 2;
s += string(left, '_') + line[0] + string(pad - left, '_');
} else {
int gaps = line.size() - 1;
int base = pad / gaps, extra = pad % gaps;
for (size_t j = 0; j < line.size(); j++) {
s += line[j];
if ((int)j < gaps) {
int sp = base + ((int)j < extra ? 1 : 0);
s += string(sp, '_');
}
}
}
out.push_back(s);
}
return out;
}You are given a grid of size rows × cols representing a haunted castle. Some cells are walls (impassable), and there are designated endpoints (start and exit). Each step you can move to an orthogonally adjacent cell (up/down/left/right) that is not a wall.
Implement classes/functions to represent the grid, walls, and endpoints, plus a function that finds a path from the start to the exit through valid cells and reports the sequence of cells visited.
Example: rows=2, cols=2, walls=[[0,1]], start=[0,0], end=[1,1] → [(0,0),(1,0),(1,1)] (length 3 = 2 steps).
解法
在 4 邻域上从 start 到 end 做标准 BFS，用 parent 表回溯路径；跳过墙和越界。复杂度 O(rows·cols)。
from collections import deque
def escape(rows, cols, walls, start, end):
blocked = set(map(tuple, walls))
if start in blocked or end in blocked:
return []
if start == end:
return [start]
parent = {start: None}
q = deque([start])
while q:
r, c = q.popleft()
if (r, c) == end:
path, cur = [], end
while cur is not None:
path.append(cur)
cur = parent[cur]
return path[::-1]
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols \
and (nr, nc) not in blocked and (nr, nc) not in parent:
parent[(nr, nc)] = (r, c)
q.append((nr, nc))
return []import java.util.*;
class Solution {
static List<int[]> escape(int rows, int cols, int[][] walls, int[] start, int[] end) {
Set<Long> blocked = new HashSet<>();
for (int[] w : walls) blocked.add((long) w[0] * cols + w[1]);
long sk = (long) start[0] * cols + start[1];
long ek = (long) end[0] * cols + end[1];
if (blocked.contains(sk) || blocked.contains(ek)) return new ArrayList<>();
Map<Long, long[]> parent = new HashMap<>();
parent.put(sk, null);
Deque<int[]> q = new ArrayDeque<>();
q.offer(start);
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!q.isEmpty()) {
int[] cur = q.poll();
long ck = (long) cur[0] * cols + cur[1];
if (ck == ek) {
List<int[]> path = new ArrayList<>();
long c = ek;
while (true) {
path.add(new int[]{(int) (c / cols), (int) (c % cols)});
long[] p = parent.get(c);
if (p == null) break;
c = p[0] * cols + p[1];
}
Collections.reverse(path);
return path;
}
for (int[] d : dirs) {
int nr = cur[0] + d[0], nc = cur[1] + d[1];
long nk = (long) nr * cols + nc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
&& !blocked.contains(nk) && !parent.containsKey(nk)) {
parent.put(nk, new long[]{cur[0], cur[1]});
q.offer(new int[]{nr, nc});
}
}
}
return new ArrayList<>();
}
}#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> escape(int rows, int cols,
vector<pair<int,int>>& walls,
pair<int,int> start, pair<int,int> end) {
set<pair<int,int>> blocked(walls.begin(), walls.end());
if (blocked.count(start) || blocked.count(end)) return {};
if (start == end) return {start};
map<pair<int,int>, pair<int,int>> parent;
parent[start] = {-1, -1};
queue<pair<int,int>> q;
q.push(start);
int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
if (make_pair(r, c) == end) {
vector<pair<int,int>> path;
auto cur = end;
while (cur.first != -1) { path.push_back(cur); cur = parent[cur]; }
reverse(path.begin(), path.end());
return path;
}
for (auto& d : dirs) {
int nr = r + d[0], nc = c + d[1];
pair<int,int> np = {nr, nc};
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
&& !blocked.count(np) && !parent.count(np)) {
parent[np] = {r, c};
q.push(np);
}
}
}
return {};
}In Part 2, the castle now contains treasures. Each treasure can only be picked up once. Your objective is to escape in as few moves as possible and maximize the number of treasures collected along the way. Define a Treasure class (with position) and implement escape() that returns (min_steps, max_treasures). If unreachable, return (-1, 0).
Example: rows=3, cols=3, walls=[[1,1]], treasures=[[0,1]], start=[0,0], end=[2,2] → (4, 1).
解锁全部 1 道题的解法
题面你已经看到了 — 解法 + 三语代码 + 复杂度推导 + 边界讨论, Pro 解锁.
- 📚1000+ 道真实北美 OA, Python / Java / C++ 三语题解
- 📊个人 dashboard + 进度可视化 + 14 天活跃图
- 📝题目笔记跨设备同步 + 个人复盘库
- 🔓随时取消下次续费, Stripe Customer Portal 自助管理