[LeetCode]Word Search II

可以用类似Word Search的方法去做，对每一个string，去board里找看存不存在，但是这样效率非常不高。假设board大小m*n，string 数目为k个，平均长度为d，这样wosrt case会达到O(m*n *k*d)，空间复杂度仍然是递归的深度O(max(d))。
我们可以发现一个显而易见的缺点是，假设存在string abcde和abcdef，事实上查找这两个数的时候就会有很多重复的操作。因为他们两有相同的前缀abcde。提到这一点，我们就可以想到一个优化的思路，就是建trie，关于trie的详细介绍可以参考这篇文章。在trie中prefix相同的两个string是沿着相同的prefix path查找下来的。也就是说，如果多个string share相同的prefix，那么我们只需要找一遍这个prefix。如果我们建好trie之后，在根据trie来dfs这个board，我们就能够减少很多不必要的计算。这样的情况下worst case时间复杂度会变为O(m * n * s)，为trie的size，在sting很多的情况下，s远小于k*d。代码如下：