網易首頁 > 網易號 > 正文申請入駐

2026-05-13：單詞方塊Ⅱ。用go語言，給定一個由互不相同小寫字母組成的四字母字符串列表 words。我們要從中找出“單詞方塊”四個單詞 to

2026-05-13 00:11:26　來源: moonfdd

北京舉報

分享至

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

我們相信人工智能為普通人提供了一種“增強工具”，并致力于分享全方位的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.