2026-05-13：单词方块Ⅱ。用go语言，给定一个由互不相同小写字母组成的四字母字符串列表 words。我们要从中找出“单词方块”四个单词 to|spiderlinebreak|下标|单词方块|字典|字母|字符串|小写

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++完整代码如下：

  

  

  


 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 
 ; 
 
 
 }