Leetcode 425

Leetcode 425 Word Square

题意：找所有满足要求的能够成对称矩阵的字符串的合集
代码：https://leetcode.com/problems/word-squares/description/

    class Solution{
    public:
        struct TrieNode{
            vector<int> indexes;
            vector<TrieNode*> children;
            TrieNode():children(26,NULL){}
        };

        TrieNode* buildTree(vector<string>& words){
            TrieNode* root = new TrieNode();
            for(int i=0;i<words.size();i++){
                TrieNode* cur = root;
                for(int j=0;j<words[i].size();j++){
                    if(cur->children[words[i][j]-'a']==NULL)
                        cur->children[words[i][j]-'a'] = new TrieNode();
                    cur = cur->children[words[i][j]-'a'];
                    cur->indexes.push_back(i);
                }
            }
            return root;
        }

        vector<vector<string>> wordSquares(vector<string> words){
            TrieNode* root = buildTree(words);
            vector<string> out(words[0].size()):
            for(int i=0;i<words.size();i++){
                out[0] = words[i];
                helper(words, root, 1, out, res);
            }
            return res;
        }

        void helper(vector<string>& words, TreeNode* root, int level, vector<string>& out, vector<vector<string>>& res){
            if(level>=out.size()){
                res.push_back(out);
                return;
            }
            string str = "";
            for(int i=0;i<level; i++){
                str+=out[i][level];
            }
            TreeNode* cur = root;
            for(int i=0;i<level; i++){
                if(cur->children[str[i]-'a'] == NULL) cur=cur->children[str[i]-'a];
                cur = cur->children[str[i]-'a'];
            }

            for(int idx:cur->indexes){
                out[level] = words[idx];
                helper(words, root, level+1, out, res);
            }

        }


    }