Leetcode Word Search搜索文中单词

Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Givenboard=

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word="ABCCED", -> returnstrue,
word="SEE", -> returnstrue,
word="ABCB", -> returnsfalse.

这道题乍一看，有够难的题目了。不过思想又是一条分支递归回溯法，对这个方法熟悉的就不难了。

是条繁题，情况多，要理清也不容易。

这些题目思路稍微有一点乱就会如乱麻一般难以解开，如果面试遇上这样的题目，又紧张的话，那么会惨啦。

一定要注意利用一切手段理清自己的思路：画图，画表，一个判断一个判断，一个问题一个问题地解决。

本题卡住的一个知识点：离散数学的逻辑判断没写好，判断错误，结果就错误了。当遇上要连接两个判断条件的时候就要非常小心，运用好离散数学的知识。

下面程序注释的很详细了。

class Solution {
public:
	bool exist(vector<vector<char> > &board, string word) 
	{
		if (board.empty() && word.empty()) return true;
		else if (board.empty()) return false;

		int row = board.size(), col = board[0].size();
		vector<vector<bool> > table(row, vector<bool>(col));

		for (int i = 0; i < row; i++)
		{
			for (int j = 0; j < col; j++)
			{
				if(onePosTest(board,table, word, 0, i, j)) 
					return true;
			}
		}
		return false;
	}

	bool onePosTest(vector<vector<char> > &board, vector<vector<bool> > &table,
		string &word, int w_start, int i, int j) 
	{
		//注意：判断顺序不能乱
		//情况1：超界，返回
		if (i>=board.size() || i <0 || j<0 || j>=board[0].size()) return false;

		//情况3：不相等，或者遍历过了的点，重置table，返回false
		if (table[i][j] || board[i][j] != word[w_start]) return false;

		//情况2：相等且没遍历过的点，置table标志位真
		table[i][j] = true;
		//情况4：找到，结束，返回真
		if (w_start == word.size()-1) return true;

		//分支递归：
		if (onePosTest(board, table, word, w_start+1, i, j+1)
		||  onePosTest(board, table, word, w_start+1, i+1, j)
		||  onePosTest(board, table, word, w_start+1, i-1, j)
		||  onePosTest(board, table, word, w_start+1, i, j-1))
		{
			return true;
		}
		table[i][j] = false;
		return false;
	}
};

O(1)空间复杂度：

//2014-2-12 update
	bool exist(vector<vector<char> > &board, string word) 
	{
		if (board.empty() || board[0].empty()) return false;

		for (int i = 0; i < board.size(); i++)
			for (int j = 0; j < board[0].size(); j++)
				if (help(board, i, j, word)) return true;

		return false;
	}
	bool help(vector<vector<char> > &board, int row, int col, 
		string &word, int begin = 0)
	{
		if (begin == word.size()) return true;
		if (row<0 || row>=board.size() || col<0 || col>=board[0].size() 
			|| board[row][col] != word[begin]) return false;
		
		char t = board[row][col];
		board[row][col] = '*';
		if (help(board, row+1, col, word, begin+1)
			|| help(board, row, col+1, word, begin+1)
			|| help(board, row-1, col, word, begin+1)
			|| help(board, row, col-1, word, begin+1))
			return true;
		board[row][col] = t;
		return false;
	}