425. Word Squares

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

Given a set of words (without duplicates), find all word squares you can build from them.

A sequence of words forms a valid word square if the kth row and column read the exact same string, where 0 ≤ k < max(numRows, numColumns).

For example, the word sequence ["ball","area","lead","lady"] forms a word square because each word reads the same both horizontally and vertically.

b a l l
a r e a
l e a d
l a d y

Note:

1. There are at least 1 and at most 1000 words.

2. All words will have the exact same length.

3. Word length is at least 1 and at most 5.

4. Each word contains only lowercase English alphabet a-z.

Example 1:

Input:
["area","lead","wall","lady","ball"]

Output:
[
  [ "wall",
    "area",
    "lead",
    "lady"
  ],
  [ "ball",
    "area",
    "lead",
    "lady"
  ]
]

Explanation:
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).

Example 2:

Input:
["abat","baba","atan","atal"]

Output:
[
  [ "baba",
    "abat",
    "baba",
    "atan"
  ],
  [ "baba",
    "abat",
    "baba",
    "atal"
  ]
]

Explanation:
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).

给无重复且等长的一堆字符串，让返回它们能形成的所有word square，word sqaure是由等长字符串组成的矩阵，要求相同编号的行和列字符串也相同。返回所有=>DFS。DFS时不断往下遍历行，在新的一行里需要找满足根据前面行生成的已有前缀下的字符串作为候选。找满足前缀的字符串=> trie。类似design autocomplete把每个trie上的前缀节点后面所接的单词存在该结点，用于方便在DFS时找候选。

参考了这。

class Solution {
public:
    class TrieNode {
    public:
        vector<TrieNode*> children;
        vector<int> words;
        TrieNode(): children(26) {}
    };
    
    void insert(TrieNode *root, const string &w, int index) {
        auto cur = root;
        for (const auto ch : w) {
            int c = ch - 'a';
            if (cur->children[c] == nullptr) {
                cur->children[c] = new TrieNode();
            }
            cur = cur->children[c];
            cur->words.push_back(index);
        }
    }
    
    void dfs(vector<string> &words, TrieNode *root, int r, vector<string> &path, vector<vector<string>> &res) {
        if (r == words[0].size()) {
            res.push_back(path);
            return;
        }
        string s;
        for (int i = 0; i < r; ++i) {
            s += path[i][r];
        }
        auto cur = root;
        for (const auto c : s) {
            if (cur->children[c - 'a'] == nullptr) return;
            cur = cur->children[c - 'a'];
        }
        for (const auto i : cur->words) {
            path[r] = words[i];
            dfs(words, root, r + 1, path, res);
        }
    }
    
    vector<vector<string>> wordSquares(vector<string>& words) {
        vector<vector<string>> res;
        if (words.size() == 0) return res;
        auto root = new TrieNode();
        for (int i = 0; i < words.size(); ++i) insert(root, words[i], i);
        vector<string> path(words[0].size());
        for (const auto &w : words) {
            path[0] = w;
            dfs(words, root, 1, path, res);
        }
        return res;
    }
};