[LeetCode] 79. Word Search

轉自LeetCode

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 =

[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

<Solution>

典型使用 DFS 來解的題目

這邊有個地方可以注意一下

一般的做法是會再用一個 2D matrix 來紀錄是否拜訪過

但這題其實可以直接把原本的字元，替換成 *，來代表拜訪過了（當然是因為本題沒用到*）

這樣不但省空間，而且速度也快很多

code 如下

c++

	class Solution {
	private:
	int m,n;
	public:
	bool exist(vector<vector<char>>& board, string word) {
	m = board.size();
	n = board[0].size();
	//> dfs
	for(int r = 0; r < m; r++) {
	for(int c = 0; c < n; c++) {
	if(dfs(0, word, r, c, board)) {
	return true;
	}
	}
	}
	return false;
	}
	bool dfs(const int &index, const string &word, const int &row, const int &col, vector<vector<char>> &board) {
	if(index == word.length()) {
	return true;
	}
	else if(row < 0 || row >= m || col < 0 || col >=n || board[row][col] != word[index]) {
	return false;
	}
	char ch = board[row][col];
	board[row][col] = '*'; //> visited
	bool res = dfs(index+1, word, row, col-1, board) || //> left
	dfs(index+1, word, row, col+1, board) || //> right
	dfs(index+1, word, row-1, col, board) || //> up
	dfs(index+1, word, row+1, col, board); //> down
	board[row][col] = ch; //> non-visited
	return res;
	}
	};

view raw wordSearchInMatrix.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	fun exist(board: Array<CharArray>, word: String): Boolean {
	for(r in board.indices) {
	for(c in board[0].indices) {
	if(dfs(0, r, c, board, word)) {
	return true
	}
	}
	}
	return false
	}
	fun dfs(index: Int, row: Int, col: Int, board: Array<CharArray>, word: String): Boolean {
	when {
	index == word.length -> return true
	row < 0 -> return false
	col < 0 -> return false
	row > board.lastIndex -> return false
	col > board[0].lastIndex -> return false
	board[row][col] != word[index] -> return false
	}
	val tmp = board[row][col]
	board[row][col] = '*'
	val res = dfs(index+1, row-1, col, board, word)
	|| dfs(index+1, row+1, col, board, word)
	|| dfs(index+1, row, col-1, board, word)
	|| dfs(index+1, row, col+1, board, word)
	board[row][col] = tmp
	return res
	}
	}

view raw word_search.kt hosted with ❤ by GitHub