北京
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.
