Leetcode: Word Search

题目

https://oj.leetcode.com/problems/word-search/

分析

  1. 通过递归来实现的DFS搜索。

  2. 需要注意的一点是, 要用一个visited二维vector来记录已经访问的元素, 以后不能再访问了。

  3. visited形参要声明成引用形式, 每次递归后手动的恢复现场。 如果声明成变量的形式, 会超时。

代码

class Solution
{
public:
	bool exist(vector<vector<char>> &board, string word)
	{
		vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size(), false));
		for (int i = 0; i < board.size(); i++)
		{
			for (int j = 0; j < board[0].size(); j++)
			{
				if (board[i][j] == word[0])
					if (search(board, i, j, word, 0, visited))
						return true;
			}
		}
		return false;
	}

	bool search(vector<vector<char>> &board, int i, int j, string word, int index, vector<vector<bool>> &visited)
	{
		if (index == word.size())
			return true;
		else if (i < 0 || i == board.size() || j < 0 || j == board[0].size())
			return false;
		else if (visited[i][j] == true)
			return false;
		else if (board[i][j] != word[index])
			return false;
		else
		{
			visited[i][j] = true;
			if (search(board, i-1, j, word, index+1, visited)) return true;
			if (search(board, i+1, j, word, index+1, visited)) return true;
			if (search(board, i, j-1, word, index+1, visited)) return true;
			if (search(board, i, j+1, word, index+1, visited)) return true;
			visited[i][j] = false;
		}

		return false;
	}
};

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/38826685

/** * RECOMMENDED CONFIGURATION VARIABLES: EDIT AND UNCOMMENT THE SECTION BELOW TO INSERT DYNAMIC VALUES FROM YOUR PLATFORM OR CMS. * LEARN WHY DEFINING THESE VARIABLES IS IMPORTANT: https://disqus.com/admin/universalcode/#configuration-variables*/ /* var disqus_config = function () { this.page.url = PAGE_URL; // Replace PAGE_URL with your page's canonical URL variable this.page.identifier = PAGE_IDENTIFIER; // Replace PAGE_IDENTIFIER with your page's unique identifier variable }; */ (function() { // DON'T EDIT BELOW THIS LINE var d = document, s = d.createElement('script'); s.src = 'https://chenzz.disqus.com/embed.js'; s.setAttribute('data-timestamp', +new Date()); (d.head || d.body).appendChild(s); })();