[LeetCode]Word Squares

这道题要generate所有的可能，所以很明显我们应该用DFS，但是具体如何DFS呢？难道穷尽所有的可能然后一个一个判断其是否为valid word square吗？显然这样做的话时间复杂度太高了，我们考虑如何剪枝。用题目给的例子说明，假设我们先选了wall，那么第二个string，只能以a开头，假设我们第二个又选了area，那么第三个string只能以le开头，一次类推，我们要不找到一个valid的word square，要不在某一步发现以特定prefix开头的string没有了。既然我们要根据prefix来找string，一个数据结构我们应当考虑的就是Trie，具体实现可以参考链接的文章。我们只需要在每次dfs的时候找对应prefix开头的所有string即可，这样可以大大地节省时间复杂度。时间复杂度O(d^2 * n)，n为输入word的数量，显然我们会考虑每一个数打头的情况。d为每个word的长度，对于每一种情况我们最多递归d层，每一层我们用O(d)的时间寻找以特定prefix开头的string，代码如下：