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个单词必须互不相同
• 结果按字典序升序排列

二、整体解题大体过程

步骤1：对输入单词列表做字典序排序

代码第一步执行 slices.Sort(words)，作用：

• 把输入的单词按照字母从小到大排序（比如 able、area、also、echo）
• 保证最终生成的答案组合天然符合字典序要求，无需后续额外排序

步骤2：初始化回溯所需变量

为了实现不重复选择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个单词都选完，开始校验是否满足条件

步骤4：DFS 递归选择单词（核心回溯逻辑）

每一层递归都做三件事：遍历 → 选择 → 递归 → 撤销（回溯）

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、bottom
2. 严格按照题目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)（主要用于标记单词是否被选中的布尔切片）

Go完整代码如下：

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 ans

if __name__ == "__main__":
    words = ["able", "area", "echo", "also"]
    result = word_squares(words)
    print(result)

C++完整代码如下：

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

void dfs(int i,
         vector<string>& words,
         vector<int>& path,
         vector<bool>& onPath,
         vector<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<vector<string>> wordSquares(vector<string>& words) {
    vector<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<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;
}