文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給定一個單詞集合 （沒有重復(fù)），找出其中所有的 單詞方塊 。

一個單詞序列形成了一個有效的單詞方塊的意思是指從第 k 行和第 k 列 (0 ≤ k < max(行數(shù), 列數(shù))) 來看都是相同的字符串。

例如，單詞序列 ["ball","area","lead","lady"] 形成了一個單詞方塊，因?yàn)槊總€單詞從水平方向看和從豎直方向看都是相同的。

b a l l a r e a l e a d l a d y 注意： 單詞個數(shù)大于等于 1 且不超過 500。 所有的單詞長度都相同。 單詞長度大于等于 1 且不超過 5。 每個單詞只包含小寫英文字母 a-z。示例 1： 輸入： ["area","lead","wall","lady","ball"] 輸出： [[ "wall","area","lead","lady"],[ "ball","area","lead","lady"] ] 解釋： 輸出包含兩個單詞方塊，輸出的順序不重要， 只需要保證每個單詞方塊內(nèi)的單詞順序正確即可。 示例 2： 輸入： ["abat","baba","atan","atal"] 輸出： [[ "baba","abat","baba","atan"],[ "baba","abat","baba","atal"] ]解釋： 輸出包含兩個單詞方塊，輸出的順序不重要， 只需要保證每個單詞方塊內(nèi)的單詞順序正確即可。

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/word-squares
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

類似題目：程序員面試金典 - 面試題 17.25. 單詞矩陣（Trie樹+DFS回溯，hard）

• trie 的每個節(jié)點(diǎn)記錄經(jīng)過該節(jié)點(diǎn)的單詞下標(biāo)

class trie { public:bool isEnd = false;trie* next[26] = {NULL};vector<int> wd;//經(jīng)過該節(jié)點(diǎn)的單詞下標(biāo)void insert(string& s, int idx){trie *cur = this;for(int i = 0; i < s.size(); ++i){if(!cur->next[s[i]-'a'])cur->next[s[i]-'a'] = new trie();cur = cur->next[s[i]-'a'];cur->wd.push_back(idx);}cur->isEnd = true;} }; class Solution {vector<vector<string>> ans;int n; public:vector<vector<string>> wordSquares(vector<string>& words) {trie* t = new trie();for(int i = 0; i < words.size(); ++i)t->insert(words[i], i);n = words[0].size();vector<string> mat;for(auto& w : words){mat.push_back(w);//以每個單詞為1第一行，開始查找dfs(words, t, mat, 1);mat.pop_back();}return ans;}void dfs(vector<string>& words, trie* t, vector<string>& mat, int len){if(len == n){ans.push_back(mat);return;}string nextprefix;//獲取下一行的前綴for(int i = 0; i < len; ++i)nextprefix += mat[i][len];trie* cur = t;for(int i = 0; i < nextprefix.size(); ++i){ //在trie中檢查前綴是否存在if(!cur->next[nextprefix[i]-'a']) return;cur = cur->next[nextprefix[i]-'a'];}for(int wd_idx : cur->wd){ //存在前綴，在當(dāng)前節(jié)點(diǎn)的單詞中加入下一個單詞mat.push_back(words[wd_idx]);dfs(words, t, mat, len+1);mat.pop_back();}} };

160 ms 16.9 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關(guān)注我的公眾號（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 425. 单词方块（Trie树+DFS）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。