?LeetCode刷題實戰(zhàn)425：單詞方塊

示例 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)的單詞順序正確即可。

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????????????string?prefix="";
????????????for(int?j=0;j????????????????prefix+=words[i][j];
????????????????mp[prefix].insert(i);
????????????}
????????}
????????for(int?i=0;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<
????????// }cout<<"-----------------"<
????????if(cur.size()>=limit){//加入結(jié)果數(shù)組
????????????vector<string> cur_res;
????????????for(int?i=0;i????????????????cur_res.emplace_back(words[cur[i]]);
????????????}
????????????res.emplace_back(move(cur_res));
????????????return;
????????}
????????string?prefix="";//先算下一個單詞需要滿足的前綴
????????for(int?j=0;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();
????????????}
????????}
????}
};