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,
Given board =

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

這道題乍一看，有夠難的題目了。不過思想又是一條分支遞歸回溯法，對這個方法熟悉的就不難了。

是條繁題，情況多，要理清也不容易。

這些題目思路稍微有一點亂就會如亂麻一般難以解開，如果面試遇上這樣的題目，又緊張的話，那麼會慘啦。

一定要注意利用一切手段理清自己的思路：畫圖，畫表，一個判斷一個判斷，一個問題一個問題地解決。

本題卡住的一個知識點：離散數學的邏輯判斷沒寫好，判斷錯誤，結果就錯誤了。當遇上要連接兩個判斷條件的時候就要非常小心，運用好離散數學的知識。

下面程序注釋的很詳細了。

class Solution {
public:
	bool exist(vector > &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 > table(row, vector(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 > &board, vector > &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;
	}
};