79. Word Search ​

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
	if (!board) {
		return false
	}

	const m = board.length
	const n = board[0].length

	for (let i = 0; i < m; i++) {
		for (let j = 0; j < n; j++) {
			if (find(board, m, n, word, i, j)) {
				return true
			}
		}
	}

	return false
};

function find(board, m, n, word, i, j) {
	if (!word) {
		return true
	}

	if (i < 0 || i >= m || j < 0 || j >= n) {
		return false
	}

	if (board[i][j] !== word[0]) {
		return false
	}

	const c = board[i][j]
	const subword = word.slice(1)
	board[i][j] = ''
	const r = find(board, m, n, subword, i + 1, j) ||
		find(board, m, n, subword, i - 1, j) ||
		find(board, m, n, subword, i, j + 1) ||
		find(board, m, n, subword, i, j - 1)
	board[i][j] = c

	return r
}