[LeetCode] 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:

There are at least 1 and at most 1000 words.
All words will have the exact same length.
Word length is at least 1 and at most 5.
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).

这道题是之前那道 Valid Word Square 的延伸，由于要求出所有满足要求的单词平方，所以难度大大的增加了，不要幻想着可以利用之前那题的解法来暴力破解，OJ 不会答应的。那么根据以往的经验，对于这种要打印出所有情况的题的解法大多都是用递归来解，那么这题的关键是根据前缀来找单词，如果能利用合适的数据结构来建立前缀跟单词之间的映射，使得我们能快速的通过前缀来判断某个单词是否存在，这是解题的关键。对于建立这种映射，这里主要有两种方法，一种是利用 HashMap 来建立前缀和所有包含此前缀单词的集合之前的映射，第二种方法是建立前缀树 Trie，顾名思义，前缀树专门就是为这种问题设计的。首先来看第一种方法，用 HashMap 来建立映射的方法，就是取出每个单词的所有前缀，然后将该单词加入该前缀对应的集合中去，然后建立一个空的 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 {

public:

    vector<vector<string>> wordSquares(vector<string>& words) {

        vector<vector<string>> res;

        unordered_map<string, set<string>> m;

        int n = words[].size();

        for (string word : words) {

            for (int i = ; i < n; ++i) {

                string key = word.substr(, i);

                m[key].insert(word);

            }

        }

        vector<vector<char>> mat(n, vector<char>(n));

        helper(, n, mat, m, res);

        return res;

    }

      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 = ; 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 + ;

            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 + ))) break;

            }

            if (j == n) helper(i + , n, mat, m, res);

        }

    }

};

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

解法二：

class Solution {

public:

    struct TrieNode {

        vector<int> indexs;

        vector<TrieNode*> children;

        TrieNode(): children(, nullptr) {}

    };

    TrieNode* buildTrie(vector<string>& words) {

        TrieNode *root = new TrieNode();

        for (int i = ; i < words.size(); ++i) {

            TrieNode *t = root;

            for (int j = ; j < words[i].size(); ++j) {

                if (!t->children[words[i][j] - 'a']) {

                    t->children[words[i][j] - 'a'] = new TrieNode();

                }

                t = t->children[words[i][j] - 'a'];

                t->indexs.push_back(i);

            }

        }

        return root;

    }

    vector<vector<string>> wordSquares(vector<string>& words) {

        TrieNode *root = buildTrie(words);

        vector<string> out(words[].size());

        vector<vector<string>> res;

        for (string word : words) {

            out[] = word;

            helper(words, , root, out, res);

        }

        return res;

    }

    void helper(vector<string>& words, int level, TrieNode* root, vector<string>& out, vector<vector<string>>& res) {

        if (level >= words[].size()) {

            res.push_back(out);

            return;

        }

        string str = "";

        for (int i = ; i < level; ++i) {

            str += out[i][level];

        }

        TrieNode *t = root;

        for (int i = ; i < str.size(); ++i) {

            if (!t->children[str[i] - 'a']) return;

            t = t->children[str[i] - 'a'];

        }

        for (int idx : t->indexs) {

            out[level] = words[idx];

            helper(words, level + , root, out, res);

        }

    }

};

Github 同步地址：

https://github.com/grandyang/leetcode/issues/425

类似题目：

Valid Word Square

参考资料：

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

https://leetcode.com/problems/word-squares/discuss/91380/java-53ms-dfs-hashmap

https://leetcode.com/problems/word-squares/discuss/91344/Short-PythonC%2B%2B-solution

https://leetcode.com/problems/word-squares/discuss/91333/Explained.-My-Java-solution-using-Trie-126ms-1616

https://leetcode.com/problems/word-squares/discuss/91337/70ms-Concise-C%2B%2B-Solution-Using-Trie-and-Backtracking

LeetCode All in One 题目讲解汇总(持续更新中...)

巴特西

[LeetCode] Word Squares 单词平方

最新文章

热门文章