今天和大家聊的问题叫做 单词方块，我们先来看题面：https://leetcode-cn.com/problems/word-squares/
示例
示例 1： 输入： ["area","lead","wall","lady","ball"] 输出： [ [ "wall", "area", "lead", "lady" ], [ "ball", "area", "lead", "lady" ] ] 解释： 输出包含两个单词方块，输出的顺序不重要，只需要保证每个单词方块内的单词顺序正确即可。 示例 2： 输入： ["abat","baba","atan","atal"] 输出： [ [ "baba", "abat", "baba", "atan" ], [ "baba", "abat", "baba", "atal" ] ] 解释： 输出包含两个单词方块，输出的顺序不重要，只需要保证每个单词方块内的单词顺序正确即可。
解题
思路 ：开始直接暴力dfs妥妥的超时。正确做法是利用前缀特性，即
如果我们知道结果中第一个单词，那么下一个单词前缀我们是知道的。
比如有[ball]，我们知道单词方块是 4X4，换句话说每个单词长度都为4，其次下个单词是a字母开头的。
假如我们找到一个a开头长度为4单词，变成[ball, area]，那么第三个单词的前缀是le长度为4单词，依次类推。
class Solution { public: int limit; unordered_map<string,unordered_set<int>> mp; vector<vector<string>> wordSquares(vector<string>& words) { if(words.empty() or words[0].empty()){return {};} vector<vector<string>> res; limit=words[0].size(); vector<int> cur; for(int i=0;i<words.size();++i){ string prefix=""; for(int j=0;j<words[i].size();++j){ prefix+=words[i][j]; mp[prefix].insert(i); } } for(int i=0;i<words.size();++i){ cur.emplace_back(i); dfs(res,words,cur); cur.pop_back(); } return res; } void dfs(vector<vector<string>>& res,vector<string>& words,vector<int>& cur){ // for(int x:cur){ // cout<<words[x]<<endl; // }cout<<"-----------------"<<endl; if(cur.size()>=limit){//加入结果数组 vector<string> cur_res; for(int i=0;i<cur.size();++i){ cur_res.emplace_back(words[cur[i]]); } res.emplace_back(move(cur_res)); return; } string prefix="";//先算下一个单词需要满足的前缀 for(int j=0;j<cur.size();++j){ prefix+=words[cur[j]][cur.size()]; } if(mp.count(prefix)){ for(int i:mp[prefix]){ cur.push_back(i); dfs(res,words,cur); cur.pop_back(); } } } };
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
