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

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

北京舉報(bào)

分享至

2026-05-13：單詞方塊Ⅱ。用go語言，給定一個(gè)由互不相同小寫字母組成的四字母字符串列表 words。我們要從中找出“單詞方塊”四個(gè)單詞 top、left、right、bottom（全部不同），并滿足它們在字母位置上的對應(yīng)關(guān)系：

? top 的第 1 個(gè)字母（索引 0）必須等于 left 的第 1 個(gè)字母（索引 0）
? top 的第 4 個(gè)字母（索引 3）必須等于 right 的第 1 個(gè)字母（索引 0）
? bottom 的第 1 個(gè)字母（索引 0）必須等于 left 的第 4 個(gè)字母（索引 3）
? bottom 的第 4 個(gè)字母（索引 3）必須等于 right 的第 4 個(gè)字母（索引 3）

也就是說，這四個(gè)單詞的首尾字母要在“上/下行、左/右列”四個(gè)角點(diǎn)位置嚴(yán)格匹配，從而形成滿足條件的方塊。

要求輸出所有不同的滿足條件的方塊，并按字典序?qū)?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"]]。

解釋:

有且僅有兩個(gè)符合題目要求的四字母單詞方塊：

"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。

單詞方塊Ⅱ解題過程詳細(xì)步驟一、題目核心要求回顧

我們要從4個(gè)字母的單詞列表中，選出4個(gè)完全不同的單詞：top、left、right、bottom，滿足4個(gè)角的字母匹配規(guī)則：

1. top[0] = left[0]（左上角相同）
2. top[3] = right[0]（右上角相同）
3. bottom[0] = left[3]（左下角相同）
4. bottom[3] = right[3]（右下角相同）

最終要求：

? 找出所有滿足條件的組合
? 4個(gè)單詞必須互不相同
? 結(jié)果按字典序升序排列

二、整體解題大體過程步驟1：對輸入單詞列表做字典序排序

代碼第一步執(zhí)行slices.Sort(words)，作用：

? 把輸入的單詞按照字母從小到大排序（比如able、area、also、echo）
? 保證最終生成的答案組合天然符合字典序要求，無需后續(xù)額外排序

步驟2：初始化回溯所需變量

為了實(shí)現(xiàn)不重復(fù)選擇4個(gè)不同單詞，代碼初始化了3個(gè)關(guān)鍵變量：

1.path：長度為4的數(shù)組，專門用來存儲(chǔ)選中的4個(gè)單詞的下標(biāo)

? path[0] → top 單詞的下標(biāo)
? path[1] → left 單詞的下標(biāo)
? path[2] → right 單詞的下標(biāo)
? path[3] → bottom 單詞的下標(biāo)

2.onPath：布爾類型切片，長度和單詞列表一致

? 作用：標(biāo)記某個(gè)單詞是否已經(jīng)被選中，避免重復(fù)選（保證4個(gè)單詞全部不同）

3.ans：最終結(jié)果集合，存儲(chǔ)所有符合條件的4單詞組合

步驟3：啟動(dòng)深度優(yōu)先搜索（DFS）回溯

從i=0開始執(zhí)行DFS，i代表當(dāng)前要選第幾個(gè)位置的單詞：

? i=0 → 選 top
? i=1 → 選 left
? i=2 → 選 right
? i=3 → 選 bottom
? i=4 → 4個(gè)單詞都選完，開始校驗(yàn)是否滿足條件

步驟4：DFS 遞歸選擇單詞（核心回溯邏輯）

每一層遞歸都做三件事：遍歷 → 選擇 → 遞歸 → 撤銷（回溯）

1.遍歷所有單詞：逐個(gè)檢查單詞是否被選中（onPath[j]）
2.未被選中則選擇：

? 把當(dāng)前單詞下標(biāo)存入path[i]
? 標(biāo)記onPath[j] = true（代表這個(gè)單詞已用，不能再選）

3.進(jìn)入下一層遞歸：繼續(xù)選下一個(gè)位置的單詞（i+1）

4.回溯撤銷選擇：遞歸返回后，把onPath[j]改回false，恢復(fù)狀態(tài)，繼續(xù)嘗試下一個(gè)單詞

這個(gè)過程會(huì)窮舉所有「4個(gè)不同單詞」的排列組合，不遺漏任何可能。

步驟5：4個(gè)單詞選滿后，校驗(yàn)是否符合條件

當(dāng)i=4時(shí)，說明已經(jīng)選好了4個(gè)不同單詞：

1. 從path中取出4個(gè)下標(biāo)，對應(yīng)拿到top、left、right、bottom
2. 嚴(yán)格按照題目4條規(guī)則校驗(yàn)字母：

? top[0] == left[0]
? top[3] == right[0]
? bottom[0] == left[3]
? bottom[3] == right[3]

3.校驗(yàn)通過：把這4個(gè)單詞組成切片，加入最終結(jié)果ans

4.校驗(yàn)不通過：直接返回，不加入結(jié)果

步驟6：遞歸全部結(jié)束，返回最終答案

所有排列組合遍歷完成后，ans里就是所有滿足條件、且按字典序排序的單詞方塊。

三、以示例輸入具體推演（幫助理解）

輸入：["able","area","echo","also"]
排序后：able、area、also、echo

1. 第一輪組合：
top=able，left=area，right=echo，bottom=also
→ 滿足所有角字母規(guī)則 → 加入答案
2. 第二輪組合：
top=area，left=able，right=also，bottom=echo
→ 滿足所有角字母規(guī)則 → 加入答案
3. 其他所有組合：
都會(huì)違反字母匹配規(guī)則 → 被過濾

最終輸出：[["able","area","echo","also"],["area","able","also","echo"]]

四、時(shí)間復(fù)雜度分析核心邏輯：窮舉 4 個(gè)不同單詞的全排列

設(shè)單詞列表長度為n（題目范圍：4 ≤ n ≤15）

? 選第1個(gè)單詞：n種選擇
? 選第2個(gè)單詞：n-1種選擇
? 選第3個(gè)單詞：n-2種選擇
? 選第4個(gè)單詞：n-3種選擇

總排列數(shù) = n × (n-1) × (n-2) × (n-3)
這是指數(shù)級的排列復(fù)雜度，記為：
時(shí)間復(fù)雜度：O(n?)

補(bǔ)充：

? 每次校驗(yàn)是固定4次字符比較 → O(1)
? 排序是 O(n log n)，遠(yuǎn)小于 O(n?)，可忽略
? 整體復(fù)雜度由窮舉排列主導(dǎo)

五、額外空間復(fù)雜度分析

額外空間 = 除輸入/輸出外，代碼運(yùn)行時(shí)主動(dòng)開辟的內(nèi)存空間

1.path數(shù)組：固定長度4 → O(1)
2.onPath布爾切片：長度n → O(n)
3. DFS遞歸調(diào)用棧：最大深度固定為4（選4個(gè)單詞）→ O(1)
4. 其他臨時(shí)變量：均為常數(shù)級

總額外空間復(fù)雜度：O(n)

總結(jié)

1.解題過程：排序 → 回溯窮舉所有4單詞不重復(fù)排列 → 校驗(yàn)字母規(guī)則 → 收集合法答案
2.時(shí)間復(fù)雜度：O(n?)（n為單詞數(shù)量，核心是4層排列窮舉）
3.額外空間復(fù)雜度：O(n)（主要用于標(biāo)記單詞是否被選中的布爾切片）

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      // 從沒有選的下標(biāo)中選一個(gè)
                onPath[j] = true// 已選上
                dfs(i + 1)
                onPath[j] = false// 恢復(fù)現(xiàn)場
            }
        }
    }

     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;        
 // 從沒有選的下標(biāo)中選一個(gè) 
 
 
             onPath[j] =  
 true 
 ;   
 // 已選上 
 
 
             dfs(i +  
 1 
 , words, path, onPath, ans); 
 
 
             onPath[j] =  
 false 
 ;  
 // 恢復(fù)現(xiàn)場 
 
 
         } 
 
 
     } 
 
 
 } 
 
 
 
 
 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 
 ; 
 
 
 }

我們相信人工智能為普通人提供了一種“增強(qiáng)工具”，并致力于分享全方位的AI知識(shí)。在這里，您可以找到最新的AI科普文章、工具評測、提升效率的秘籍以及行業(yè)洞察。歡迎關(guān)注“福大大架構(gòu)師每日一題”，發(fā)消息可獲得面試資料，讓AI助力您的未來發(fā)展。

特別聲明：以上內(nèi)容(如有圖片或視頻亦包括在內(nèi))為自媒體平臺(tái)“網(wǎng)易號”用戶上傳并發(fā)布，本平臺(tái)僅提供信息存儲(chǔ)服務(wù)。

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.