[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。代码如下：

	class Solution {
	public:
	vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
	Node* root = new Node();
	for (auto& word : words)
	insert(root, word);
	int m = board.size(), n = m ? board[0].size() : 0;
	vector<string> res;
	for (int i = 0; i < m; ++i)
	{
	for (int j = 0; j < n; ++j)
	{
	char c = board[i][j];
	if (root->children[c])
	backtrack(board, res, root->children[c], string(1, c), i, j);
	}
	}
	return res;
	}
	private:
	struct Node
	{
	bool isWord;
	unordered_map<char, Node*> children;
	Node() : isWord(false)
	{
	}
	};
	void insert(Node* curr, string word)
	{
	int i = 0;
	while (i < word.size())
	{
	char c = word[i];
	if (!curr->children[c])
	curr->children[c] = new Node();
	curr = curr->children[c];
	++i;
	}
	curr->isWord = true;
	}
	void backtrack(vector<vector<char>>& board, vector<string>& res, Node* node, string curr, int x, int y)
	{
	int m = board.size(), n = m ? board[0].size() : 0;
	if (!node)return;
	if (node->isWord)
	{
	res.push_back(curr);
	node->isWord = false;
	}
	vector<pair<int, int>> dirs = { { 1, 0 },{ -1, 0 },{ 0, 1 },{ 0, -1 } };
	char c = board[x][y];
	board[x][y] = '.';
	for (auto& dir : dirs)
	{
	int i = x + dir.first, j = y + dir.second;
	if (i >= 0 && i < m && j >= 0 && j < n && board[i][j] != '.' && node->children.find(board[i][j]) != node->children.end())
	backtrack(board, res, node->children[board[i][j]], curr + board[i][j], i, j);
	}
	board[x][y] = c;
	}
	};

view raw Word Search II.cpp hosted with ❤ by GitHub