425. Word Squares (Hard)

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 k th 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).
Show Company Tags
Show Tags
Show Similar Problems

Solution 1: Hash Table, DFS 722ms

这道题是之前那道Valid Word Square的延伸，由于要求出所有满足要求的单词平方，所以难度大大的增加了，不要幻想着可以利用之前那题的解法来暴力破解，OJ不会答应的。那么根据以往的经验，对于这种要打印出所有情况的题的解法大多都是用递归来解，那么这题的关键是根据前缀来找单词，我们如果能利用合适的数据结构来建立前缀跟单词之间的映射，使得我们能快速的通过前缀来判断某个单词是否存在，这是解题的关键。对于建立这种映射，这里主要有两种方法，一种是利用哈希表来建立前缀和所有包含此前缀单词的集合之前的映射，第二种方法是建立前缀树Trie，顾名思义，前缀树专门就是为这种问题设计的。那么我们首先来看第一种方法，用哈希表来建立映射的方法，我们就是取出每个单词的所有前缀，然后将该单词加入该前缀对应的集合中去，然后我们建立一个空的nxn的char矩阵，其中n为单词的长度，我们的目标就是来把这个矩阵填满，我们从0开始遍历，我们先取出长度为0的前缀，即空字符串，由于我们在建立映射的时候，空字符串也和每个单词的集合建立了映射，然后我们遍历这个集合，用遍历到的单词的i位置字符，填充矩阵mat[i][i]，然后j从i+1出开始遍历，对应填充矩阵mat[i][j]和mat[j][i]，然后我们根据第j行填充得到的前缀，到哈希表中查看有没单词，如果没有，就break掉，如果有，则继续填充下一个位置。最后如果j==n了，说明第0行和第0列都被填好了，我们再调用递归函数，开始填充第一行和第一列，依次类推，直至填充完成，参见代码如下：

class Solution {
    void helper(int i, int n, vector<vector<char>>& mat, unordered_map<string, set<string>>& m, vector<vector<string>>& res) {
        if (i == n) {
            vector<string> out;
            for (int j = 0; j < n; ++j) out.push_back(string(mat[j].begin(), mat[j].end()));
            res.push_back(out);
            return;
        }
        string key = string(mat[i].begin(), mat[i].begin()+i);

        for (string str: m[key]) {
            mat[i][i] = str[i];
            int j = i+1;
            for (; j < n; ++j) {
                mat[i][j] = str[j];
                mat[j][i] = str[j];
                if (!m.count(string(mat[j].begin(), mat[j].begin()+i+1))) break;
            }
            if (j == n) helper(i+1, n, mat, m, res);
        }

    }
public:
    vector<vector<string>> wordSquares(vector<string>& words) {
        vector<vector<string>> res;
        unordered_map<string, set<string>> m;
        int n = words[0].size();
        for (string word:words) {
            for (int i = 0; i < n; ++i) {
                string key = word.substr(0,i);
                m[key].insert(word);
            }
        }
        vector<vector<char>> mat(n, vector<char>(n));
        helper(0, n, mat, m, res);
        return res;
    }
};

Solution 2:Trie, DFS 36ms

下面来看建立前缀树Trie的方法，这种方法的难点是看能不能熟练的写出Trie的定义，还有构建过程，以及后面在递归函数中，如果利用前缀树来快速查找单词的前缀，总之，这道题是前缀树的一种经典的应用，能白板写出来就说明基本上已经掌握了前缀树了，参见代码如下：

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

    TrieNode* buildTrie(vector<string>& words) {
        TrieNode* root = new TrieNode();
        for (int i = 0; i < words.size(); ++i) {
            TrieNode* p = root;
            p->idx.push_back(i);
            for (int j = 0; j < words[i].size(); ++j) {
                int pos = words[i][j]-'a';
                if (!p->children[pos]) p->children[pos] = new TrieNode();
                p = p->children[pos];
                p->idx.push_back(i);
            }
        }
        return root;
    }

    void helper(vector<string>& words, int level, TrieNode* root, vector<string>& out, vector<vector<string>>& res) {
        if (level == words[0].size()) {
            res.push_back(out);
            return;
        }
        string prefix;
        for (int i = 0; i < level; ++i) {
            prefix += out[i][level];
        }
        TrieNode* p = root;
        for (char c: prefix) {
            if (!p->children[c-'a']) return;
            p = p->children[c-'a'];
        }
        for (int i: p->idx) {
            out[level] = words[i];
            helper(words, level+1, root, out, res);
        }
    }
public:
    vector<vector<string>> wordSquares(vector<string>& words) {
        TrieNode* root = buildTrie(words);
        vector<vector<string>> res;
        vector<string> out(words[0].size());
        helper(words, 0, root, out, res);
        return res;
    }
};