Leetcode79 method 1: deep search

79. Word search
    Given a two-dimensional grid and a word , Find out if the word exists in the grid .

The words must be in alphabetical order , It's made up of letters in adjacent cells , among “ adjacent ” Cells are those adjacent horizontally or vertically . Letters in the same cell are not allowed to be reused .

Example :

board =
[
[‘A’,‘B’,‘C’,‘E’],
[‘S’,‘F’,‘C’,‘S’],
[‘A’,‘D’,‘E’,‘E’]
]

Given word = “ABCCED”, return true
Given word = “SEE”, return true
Given word = “ABCB”, return false

Tips ：

board and word Contains only uppercase and lowercase letters .
1 <= board.length <= 200
1 <= board[i].length <= 200
1 <= word.length <= 10^3

Execution time : 184 ms
Memory consumption : 120.8 MB

class Solution {
    
public:
	bool check(vector<vector<char>>& board, vector<vector<int>>& visited, string word, int i, int j, int k, int h, int w) {
    
		//i j Is the coordinate of the current point  k Is used to mark which character needs to be queried 
		/*  Two logics   If this element is not, then go back   If it has been found, exit  */

		if (board[i][j] != word[k]) {
    
			return false;
		}
		else if (k == word.length() - 1) {
    
			return true;
		}
		// Set up visited
		visited[i][j] = 1;

		// Found this element but didn't end 

		k += 1;// If you find this element, you can self increase 
		int temp_i;
		int temp_j;
		// Set offset 
		vector<pair<int, int>>direction{
     {
    0, 1},{
    0 ,-1},{
    1, 0},{
    -1, 0} };// Right   Left   On   Next 
		for (int n = 0; n < 4; n++) {
    
			temp_i = i + direction[n].first;
			temp_j = j + direction[n].second;
			if (temp_i == h || temp_j == w || temp_i == -1 || temp_j == -1)continue;

			if (!visited[temp_i][temp_j]) {
    
				//cout << "(" << temp_i + 1 << "," << temp_j + 1 << ")" << endl;
				if (check(board, visited, word, temp_i, temp_j, k, h, w))return true;
			}
		}

		// After four cycles, it is found that no usable element can be found   Restore it to 0  That's important 
		visited[i][j] = 0;

		return false;

	}


	bool exist(vector<vector<char>>& board, string word) {
    
		int i, j, k;
		int h = board.size(), w = board[0].size();
		// Get the position of the first letter   Determine the starting point 
		char star = word[0];// Get the first letter 

		vector<int>coordinate;// Store coordinates 


		// The coordinates were successfully stored in coordinate in 
		for (i = 0; i < h; i++) {
    
			for (j = 0; j < w; j++) {
    
				if (board[i][j] == star) {
    
					
						coordinate.push_back(i);
						coordinate.push_back(j);
					
				}
			}
		}


		// Initialize a check matrix   The checked element is set to 1
		vector<vector<int>> visited(h, vector<int>(w, 0));

		//DFS start-up 
		bool flag;
		for (k = 0; k < coordinate.size() / 2; k++) {
    
			flag = check(board, visited, word, coordinate[k * 2], coordinate[k * 2 + 1], 0, h, w);
			if (flag) return true;
			// hold visited All set to 0
			
			vector<vector<int>> visited(h, vector<int>(w, 0));
		}

		return false;
	}
};

Appropriate optimization ：
Don't open up too many new visited Repeated use
Yes word Array adopts reference
Execution time : 76 ms
Memory consumption : 17 MB

class Solution {
    
public:
	bool check(vector<vector<char>>& board, vector<vector<int>>& visited, string& word, int i, int j, int k, int h, int w) {
    
		//i j Is the coordinate of the current point  k Is used to mark which character needs to be queried 
		/*  Two logics   If this element is not, then go back   If it has been found, exit  */
		
		//cout << "(" << i+1 << "," << j+1 << ")" << endl;

		bool result = false;

		if (board[i][j] != word[k]) {
    
			return false;
		}
		else if (k == word.length() - 1) {
    
			return true;
		}
		// Set up visited
		visited[i][j] = 1;

		// Found this element but didn't end 

		k += 1;// If you find this element, you can self increase 
		int temp_i;
		int temp_j;
		// Set offset 
		vector<pair<int, int>>direction{
     {
    0, 1},{
    0 ,-1},{
    1, 0},{
    -1, 0} };// Right   Left   On   Next 
		for (int n = 0; n < 4; n++) {
    
			temp_i = i + direction[n].first;
			temp_j = j + direction[n].second;
			if (temp_i == h || temp_j == w || temp_i == -1 || temp_j == -1)continue;

			if (!visited[temp_i][temp_j]) {
    
				if (check(board, visited, word, temp_i, temp_j, k, h, w)) {
    
					result = true;
					break;
				}
			}
		}

		// After four cycles, it is found that no usable element can be found   Restore it to 0
		visited[i][j] = 0;

		return result;

	}


	bool exist(vector<vector<char>>& board, string word) {
    
		int i, j, k;
		int h = board.size(), w = board[0].size();
		// Get the position of the first letter   Determine the starting point 
		char star = word[0];// Get the first letter 

		vector<int>coordinate;// Store coordinates 


		// The coordinates were successfully stored in coordinate in 
		for (i = 0; i < h; i++) {
    
			for (j = 0; j < w; j++) {
    
				if (board[i][j] == star) {
    
					
						coordinate.push_back(i);
						coordinate.push_back(j);
					
				}
			}
		}


		// Initialize a check matrix   The checked element is set to 1
		vector<vector<int>> visited(h, vector<int>(w, 0));

		//DFS
		bool flag;
		for (k = 0; k < coordinate.size() / 2; k++) {
    
			flag = check(board, visited, word, coordinate[k * 2], coordinate[k * 2 + 1], 0, h, w);
			if (flag) return true;
			// hold visited All set to 0
			
		}

		return false;
	}
};

Optimize... Again ：
add to private To store some data and speed up the operation
Execution time ：24 ms, In all C++ Defeated in submission 93.89% Users of
Memory consumption ：8.8 MB, In all C++ Defeated in submission 44.96% Users of

class Solution {
    
private:
	vector<pair<int, int>>direction{
     {
    0, 1},{
    0 ,-1},{
    1, 0},{
    -1, 0} };// Right   Left   On   Next 
public:
	bool check(vector<vector<char>>& board, vector<vector<int>>& visited, string& word, int i, int j, int k, int h, int w) {
    
		//i j Is the coordinate of the current point  k Is used to mark which character needs to be queried 
		/*  Two logics   If this element is not, then go back   If it has been found, exit  */
		

		bool result = false;

		if (board[i][j] != word[k]) {
    
			return false;
		}
		else if (k == word.length() - 1) {
    
			return true;
		}
		// Set up visited
		visited[i][j] = 1;

		// Found this element but didn't end 

		k += 1;// If you find this element, you can self increase 
		int temp_i;
		int temp_j;
		// Set offset 

		for (int n = 0; n < 4; n++) {
    
			temp_i = i + direction[n].first;
			temp_j = j + direction[n].second;
			if (temp_i == h || temp_j == w || temp_i == -1 || temp_j == -1)continue;

			if (!visited[temp_i][temp_j]) {
    
				if (check(board, visited, word, temp_i, temp_j, k, h, w)) {
    
					result = true;
					break;
				}
			}
		}

		// After four cycles, it is found that no usable element can be found   Restore it to 0
		visited[i][j] = 0;

		return result;

	}


	bool exist(vector<vector<char>>& board, string word) {
    
		int i, j, k;
		int h = board.size(), w = board[0].size();
		// Get the position of the first letter   Determine the starting point 
		char star = word[0];// Get the first letter 

		vector<int>coordinate;// Store coordinates 


		// The coordinates were successfully stored in coordinate in 
		for (i = 0; i < h; i++) {
    
			for (j = 0; j < w; j++) {
    
				if (board[i][j] == star) {
    
					
						coordinate.push_back(i);
						coordinate.push_back(j);
					
				}
			}
		}


		// Initialize a check matrix   The checked element is set to 1
		vector<vector<int>> visited(h, vector<int>(w, 0));

		//DFS
		bool flag;
		for (k = 0; k < coordinate.size() / 2; k++) {
    
			flag = check(board, visited, word, coordinate[k * 2], coordinate[k * 2 + 1], 0, h, w);
			if (flag) return true;
			// hold visited All set to 0
			
		}

		return false;
	}
};