425

class Solution {
public:
    int n;
    unordered_map<string, vector<string>> fulls;
    vector<string> square;
    vector<vector<string>> squares;

    vector<vector<string>> wordSquares(vector<string>& words) {
        n = words[0].size();
        square.resize(n);
        for(string word : words)
            for(int i=0; i<n; i++)
                fulls[word.substr(0, i)].push_back(word);
        build(0);
        return squares;
    }

    void build(int i) {
        if(i == n) {
            squares.push_back(square);
            return;
        }
        string prefix;
        for(int k=0; k<i; k++)
            prefix += square[k][i];
        for(string word : fulls[prefix]) {
            square[i] = word;
            build(i + 1);
        }
    }
};