北京
2026-05-13：单词方块Ⅱ。用go语言，给定一个由互不相同小写字母组成的四字母字符串列表 words。我们要从中找出“单词方块”四个单词 top、left、right、bottom（全部不同），并满足它们在字母位置上的对应关系：
• top 的第 1 个字母（索引 0）必须等于 left 的第 1 个字母（索引 0）
• top 的第 4 个字母（索引 3）必须等于 right 的第 1 个字母（索引 0）
• bottom 的第 1 个字母（索引 0）必须等于 left 的第 4 个字母（索引 3）
• bottom 的第 4 个字母（索引 3）必须等于 right 的第 4 个字母（索引 3）
也就是说，这四个单词的首尾字母要在“上/下行、左/右列”四个角点位置严格匹配，从而形成满足条件的方块。
要求输出所有不同的满足条件的方块，并按字典序对 4 元组 (top, left, right, bottom) 做升序排序后返回。
4 <= words.length <= 15。
words[i].length == 4。
words[i] 仅由小写英文字母组成。
所有 words[i] 都 互不相同 。
输入: words = ["able","area","echo","also"]。
输出: [["able","area","echo","also"],["area","able","also","echo"]]。
解释:
有且仅有两个符合题目要求的四字母单词方块：
"able" (top), "area" (left), "echo" (right), "also" (bottom)
top[0] == left[0] == 'a'
top[3] == right[0] == 'e'
bottom[0] == left[3] == 'a'
bottom[3] == right[3] == 'o'
"area" (top), "able" (left), "also" (right), "echo" (bottom)
对角的所有约束均满足。
因此，答案为 [["able","area","echo","also"],["area","able","also","echo"]]。
题目来自力扣3799。
单词方块Ⅱ解题过程详细步骤 一、题目核心要求回顾
我们要从4个字母的单词列表中，选出4个完全不同的单词：top、left、right、bottom，满足4个角的字母匹配规则：
1. top[0] = left[0]（左上角相同）
2. top[3] = right[0]（右上角相同）
3. bottom[0] = left[3]（左下角相同）
4. bottom[3] = right[3]（右下角相同）
最终要求：
• 找出所有满足条件的组合
• 4个单词必须互不相同
• 结果按字典序升序排列
代码第一步执行slices.Sort(words)，作用：
• 把输入的单词按照字母从小到大排序（比如
able、area、also、echo）• 保证最终生成的答案组合天然符合字典序要求，无需后续额外排序
为了实现不重复选择4个不同单词，代码初始化了3个关键变量：
1.
path：长度为4的数组，专门用来存储选中的4个单词的下标
• path[0] → top 单词的下标
• path[1] → left 单词的下标
• path[2] → right 单词的下标
• path[3] → bottom 单词的下标
2.onPath：布尔类型切片，长度和单词列表一致
• 作用：标记某个单词是否已经被选中，避免重复选（保证4个单词全部不同）
3.ans：最终结果集合，存储所有符合条件的4单词组合
步骤3：启动深度优先搜索（DFS）回溯
从i=0开始执行DFS，i代表当前要选第几个位置的单词：
• i=0 → 选 top
• i=1 → 选 left
• i=2 → 选 right
• i=3 → 选 bottom
• i=4 → 4个单词都选完，开始校验是否满足条件
每一层递归都做三件事：遍历 → 选择 → 递归 → 撤销（回溯）
1.遍历所有单词：逐个检查单词是否被选中（
onPath[j]）2.未被选中则选择：
• 把当前单词下标存入
path[i]• 标记
onPath[j] = true（代表这个单词已用，不能再选）
3.进入下一层递归：继续选下一个位置的单词（i+1）
4.回溯撤销选择：递归返回后，把onPath[j]改回false，恢复状态，继续尝试下一个单词
这个过程会穷举所有「4个不同单词」的排列组合，不遗漏任何可能。
步骤5：4个单词选满后，校验是否符合条件
当i=4时，说明已经选好了4个不同单词：
1. 从
path中取出4个下标，对应拿到top、left、right、bottom2. 严格按照题目4条规则校验字母：
• top[0] == left[0]
• top[3] == right[0]
• bottom[0] == left[3]
• bottom[3] == right[3]
3.校验通过：把这4个单词组成切片，加入最终结果ans
4.校验不通过：直接返回，不加入结果
步骤6：递归全部结束，返回最终答案
所有排列组合遍历完成后，ans里就是所有满足条件、且按字典序排序的单词方块。
三、以示例输入具体推演（帮助理解）
输入：["able","area","echo","also"]
排序后：able、area、also、echo
1. 第一轮组合：
top=able，left=area，right=echo，bottom=also
→ 满足所有角字母规则 → 加入答案2. 第二轮组合：
top=area，left=able，right=also，bottom=echo
→ 满足所有角字母规则 → 加入答案3. 其他所有组合：
都会违反字母匹配规则 → 被过滤
最终输出：[["able","area","echo","also"],["area","able","also","echo"]]
四、时间复杂度分析 核心逻辑：穷举 4 个不同单词的全排列
设单词列表长度为n（题目范围：4 ≤ n ≤15）
• 选第1个单词：
n种选择• 选第2个单词：
n-1种选择• 选第3个单词：
n-2种选择• 选第4个单词：
n-3种选择
总排列数 = n × (n-1) × (n-2) × (n-3)
这是指数级的排列复杂度，记为：
时间复杂度：O(n⁴)
补充：
• 每次校验是固定4次字符比较 → O(1)
• 排序是 O(n log n)，远小于 O(n⁴)，可忽略
• 整体复杂度由穷举排列主导
额外空间 = 除输入/输出外，代码运行时主动开辟的内存空间
1.
path数组：固定长度4 → O(1)2.
onPath布尔切片：长度n → O(n)3. DFS递归调用栈：最大深度固定为4（选4个单词）→ O(1)
4. 其他临时变量：均为常数级
总额外空间复杂度：O(n)
总结
1.解题过程：排序 → 回溯穷举所有4单词不重复排列 → 校验字母规则 → 收集合法答案
2.时间复杂度：O(n⁴)（n为单词数量，核心是4层排列穷举）
3.额外空间复杂度：O(n)（主要用于标记单词是否被选中的布尔切片）
package main
import (
"fmt"
"slices"
)
func wordSquares(words []string) (ans [][]string) {
slices.Sort(words) // 保证答案有序
path := [4]int{}
onPath := make([]bool, len(words))
var dfs func(int)
dfs = func(i int) {
if i == 4 {
top := words[path[0]]
left := words[path[1]]
right := words[path[2]]
bottom := words[path[3]]
if top[0] == left[0] && top[3] == right[0] && bottom[0] == left[3] && bottom[3] == right[3] {
ans = append(ans, []string{top, left, right, bottom})
}
return
}
for j, on := range onPath {
if !on {
path[i] = j // 从没有选的下标中选一个
onPath[j] = true// 已选上
dfs(i + 1)
onPath[j] = false// 恢复现场
}
}
}dfs(0)
return
}
func main() {
words := []string{"able", "area", "echo", "also"}
result := wordSquares(words)
fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-
from typing import List
def word_squares(words: List[str]) -> List[List[str]]:
words.sort() # 保证答案有序
ans = []
n = len(words)
path = [0] * 4
on_path = [False] * n
def dfs(i: int):
if i == 4:
top = words[path[0]]
left = words[path[1]]
right = words[path[2]]
bottom = words[path[3]]
if (top[0] == left[0] and top[3] == right[0] and
bottom[0] == left[3] and bottom[3] == right[3]):
ans.append([top, left, right, bottom])
return
for j in range(n):
if not on_path[j]:
path[i] = j
on_path[j] = True
dfs(i + 1)
on_path[j] = False
dfs(0)
return ansif __name__ == "__main__":
words = ["able", "area", "echo", "also"]
result = word_squares(words)
print(result)
C++完整代码如下：
using namespace std;void dfs(int i,
vector& words,
vector& path,
vector& onPath,
vector string >>& ans) {
if (i == 4 ) {
string top = words[path[ 0 ]];
string left = words[path[ 1 ]];
string right = words[path[ 2 ]];
string bottom = words[path[ 3 ]];
if (top[ 0 ] == left[ 0 ] &&
top[ 3 ] == right[ 0 ] &&
bottom[ 0 ] == left[ 3 ] &&
bottom[ 3 ] == right[ 3 ]) {
ans.push_back({top, left, right, bottom});
}
return ;
}
for ( int j = 0 ; j < words.size(); j++) {
if (!onPath[j]) {
path[i] = j; // 从没有选的下标中选一个
onPath[j] = true ; // 已选上
dfs(i + 1 , words, path, onPath, ans);
onPath[j] = false ; // 恢复现场
}
}
}
vector string >> wordSquares(vector< string >& words) {
vector string >> ans;
sort(words.begin(), words.end()); // 保证答案有序
vector< int > path( 4 );
vector< bool > onPath(words.size(), false );
dfs( 0 , words, path, onPath, ans);
return ans;
}
int main() {
vector< string > words = { "able" , "area" , "echo" , "also" };
vector string >> result = wordSquares(words);
for ( const auto& square : result) {
cout << "[" ;
for ( int i = 0 ; i < square.size(); i++) {
cout << square[i];
if (i != square.size() - 1 ) {
cout << ", " ;
}
}
cout << "]" << endl;
}
return 0 ;
}
我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。
特别声明：以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布，本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
