LeetCode刷题实战425：单词方块

ゞ浴缸里的玫瑰 2022-09-17 05:23 165阅读 0赞

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！

今天和大家聊的问题叫做 **单词方块**，我们先来看题面：

https://leetcode-cn.com/problems/word-squares/

![0418a9705bf94e6a4f6faadf6f0fdfcd.png][]

![53476621ca0068c1b1341f6574ade19e.png][]

## **示例** ##

示例 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();
                }
            }
        }
    };

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个**在看**或者转发吧，你们的支持是我最大的动力 。

**上期推文：**

[LeetCode1-420题汇总，希望对你有点帮助！][LeetCode1-420]

[LeetCode刷题实战421：数组中两个数的最大异或值][LeetCode_421]

[LeetCode刷题实战422：有效的单词方块][LeetCode_422]

[LeetCode刷题实战423：从英文中重建数字][LeetCode_423]

[LeetCode刷题实战424：替换后的最长重复字符][LeetCode_424]

![7cffbb914e27cf0911d66c2cc39421b6.png][]

[0418a9705bf94e6a4f6faadf6f0fdfcd.png]: /images/20220828/1df272f06ae843e7b36571de63a170c4.png
[53476621ca0068c1b1341f6574ade19e.png]: /images/20220828/4106f66525784bcc83f8d55e50537f77.png
[LeetCode1-420]: https://blog.csdn.net/itcodexy/article/details/109832160
[LeetCode_421]: https://blog.csdn.net/itcodexy/article/details/121045858
[LeetCode_422]: https://blog.csdn.net/itcodexy/article/details/121059456
[LeetCode_423]: https://blog.csdn.net/itcodexy/article/details/120715226
[LeetCode_424]: https://blog.csdn.net/itcodexy/article/details/120582768
[7cffbb914e27cf0911d66c2cc39421b6.png]: /images/20220828/66c2f6a6cdd94569b6e710e77077539b.png