leetcode 425+lintcode 634-- TrieNode

这个题用典型的前缀树解决：

图片.png

整个代码递归过程：

图片.png

//my
class Solution {
public:
    struct TrieNode {
        vector<TrieNode*> child = vector<TrieNode*>(26, nullptr);
        vector<int> idx;
    };
    TrieNode* insert(TrieNode* root, vector<string>& words) {
        
        for (int i = 0; i < words.size(); i++) {
            TrieNode* temp = root;
            for (int j = 0; j < words[i].size(); j++) {
                if (temp->child[words[i][j] - 'a'] == nullptr)
                    temp->child[words[i][j] - 'a'] = new TrieNode();
                temp->idx.push_back(i);
                temp = temp->child[words[i][j] - 'a'];
            }
        }
        return root;
    }
    void helper(TrieNode *root, int level, vector<vector<string>>& ans, vector<string>& out, vector<string>& words) {
        if (level >= out[0].size()) {
            ans.push_back(out);
            return;
        }
        string str = "";
        for (int i = 0; i < level; i++)
            str += out[i][level];
        TrieNode* temp = root;
        for (auto cc : str) {
            if (temp->child[cc - 'a'] == nullptr)
                return;
            temp = temp->child[cc - 'a'];
        }//out of loop we point to the next node
        for (auto aa : temp->idx) {
            out[level]=(words[aa]);
            helper(root, level + 1, ans, out, words);
        }
    }
    vector<vector<string>> wordSquares(vector<string>& words) {
        TrieNode * root=new TrieNode();
        root=insert(root,words);
        vector<vector<string>> ans;
        vector<string> out(words[0].size());// not exact number
        for (auto aa : words) {
            out[0]=aa;
            helper(root, 1, ans, out,words);
        }
        return ans;
    }
};