425. Word Squares

class Solution {
public:
    vector<vector<string>> wordSquares(vector<string>& words) {
        square.resize(words[0].size());
        for (int i = 0; i < words.size(); i++)
            for (int j = 0; j < words[0].size(); j++)
                prefixDict[words[i].substr(0, j)].push_back(words[i]);
        DFS(0);
        return res;
    }
private:
    unordered_map <string, vector<string>> prefixDict;
    vector<vector<string>> res;
    vector<string> square;

    void DFS(int currLen) {
        if (currLen == square.size()) {
            res.push_back(square);
            return;
        }
        string prefix;
        for (int i = 0; i < currLen; i++)
            prefix += square[i][currLen];
        for (string word:prefixDict[prefix]) {
            square[currLen] = word;
            DFS(currLen + 1);
        }
        return;
    }
};