79. Word Search
leetcode medium
#array#backtracking#csharp#graph#leetcode#matrix#medium#prefix-sum#recursion#search#string
Task
Дана сетка символов размером m на n, называемая board, и строка word. Верните true, если слово word существует в сетке.
Слово можно составить из букв последовательно смежных ячеек, где смежные ячейки находятся рядом по горизонтали или вертикали. Одна и та же ячейка с буквой не может быть использована более одного раза.
Пример:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
C# solution
matched/originalpublic class Solution {
private char[][] board;
private int rows;
private int cols;
public bool Exist(char[][] board, string word) {
this.board = board;
this.rows = board.Length;
this.cols = board[0].Length;
for (int row = 0; row < this.rows; row++) {
for (int col = 0; col < this.cols; col++) {
if (Backtrack(row, col, word, 0)) {
return true;
}
}
}
return false;
}
private bool Backtrack(int row, int col, string word, int index) {
if (index >= word.Length) {
return true;
}
if (row < 0 || row == this.rows || col < 0 || col == this.cols ||
this.board[row][col] != word[index]) {
return false;
}
bool ret = false;
char temp = this.board[row][col];
this.board[row][col] = '#';
int[] rowOffsets = { 0, 1, 0, -1 };
int[] colOffsets = { 1, 0, -1, 0 };
for (int d = 0; d < 4; d++) {
ret = Backtrack(row + rowOffsets[d], col + colOffsets[d], word, index + 1);
if (ret)
break;
}
this.board[row][col] = temp;
return ret;
}
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
private char[][] board;
private int rows;
private int cols;
public bool Exist(char[][] board, string word) {
this.board = board;
this.rows = board.size();
this.cols = board[0].size();
for (int row = 0; row < this.rows; row++) {
for (int col = 0; col < this.cols; col++) {
if (Backtrack(row, col, word, 0)) {
return true;
}
}
}
return false;
}
private bool Backtrack(int row, int col, string word, int index) {
if (index >= word.size()) {
return true;
}
if (row < 0 || row == this.rows || col < 0 || col == this.cols ||
this.board[row][col] != word[index]) {
return false;
}
bool ret = false;
char temp = this.board[row][col];
this.board[row][col] = '#';
vector<int>& rowOffsets = { 0, 1, 0, -1 };
vector<int>& colOffsets = { 1, 0, -1, 0 };
for (int d = 0; d < 4; d++) {
ret = Backtrack(row + rowOffsets[d], col + colOffsets[d], word, index + 1);
if (ret)
break;
}
this.board[row][col] = temp;
return ret;
}
}Java solution
matched/originalclass Solution {
private char[][] board;
private int ROWS;
private int COLS;
public boolean exist(char[][] board, String word) {
this.board = board;
this.ROWS = board.length;
this.COLS = board[0].length;
for (int row = 0; row < this.ROWS; ++row) {
for (int col = 0; col < this.COLS; ++col) {
if (this.backtrack(row, col, word, 0)) return true;
}
}
return false;
}
protected boolean backtrack(int row, int col, String word, int index) {
if (index >= word.length()) return true;
if (
row < 0 ||
row == this.ROWS ||
col < 0 ||
col == this.COLS ||
this.board[row][col] != word.charAt(index)
) return false;
boolean ret = false;
this.board[row][col] = '#';
int[] rowOffsets = { 0, 1, 0, -1 };
int[] colOffsets = { 1, 0, -1, 0 };
for (int d = 0; d < 4; ++d) {
ret = this.backtrack(
row + rowOffsets[d],
col + colOffsets[d],
word,
index + 1
);
if (ret) break;
}
this.board[row][col] = word.charAt(index);
return ret;
}
}JavaScript solution
matched/originalvar exist = function (board, word) {
const ROWS = board.length;
const COLS = board[0].length;
const backtrack = function (row, col, suffix) {
if (suffix.length == 0) return true;
if (
row < 0 ||
row == ROWS ||
col < 0 ||
col == COLS ||
board[row][col] != suffix.charAt(0)
)
return false;
let ret = false;
board[row][col] = "#";
const directions = [
[0, 1],
[1, 0],
[0, -1],
[-1, 0],
];
for (let [rowOffset, colOffset] of directions) {
ret = backtrack(row + rowOffset, col + colOffset, suffix.slice(1));
if (ret) break;
}
board[row][col] = suffix.charAt(0);
return ret;
};
for (let row = 0; row < ROWS; ++row) {
for (let col = 0; col < COLS; ++col) {
if (backtrack(row, col, word)) return true;
}
}
return false;
};Python solution
matched/originalclass Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
self.ROWS = len(board)
self.COLS = len(board[0])
self.board = board
for row in range(self.ROWS):
for col in range(self.COLS):
if self.backtrack(row, col, word):
return True
return False
def backtrack(self, row: int, col: int, suffix: str) -> bool:
if len(suffix) == 0:
return True
if (row < 0 or row == self.ROWS or col < 0 or col == self.COLS or self.board[row][col] != suffix[0]):
return False
ret = False
self.board[row][col] = "#"
for rowOffset, colOffset in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
ret = self.backtrack(row + rowOffset, col + colOffset, suffix[1:])
if ret:
break
self.board[row][col] = suffix[0]
return retGo solution
matched/originalfunc exist(board [][]byte, word string) bool {
rows := len(board)
if rows == 0 {
return false
}
cols := len(board[0])
var backtrack func(row int, col int, index int) bool
backtrack = func(row int, col int, index int) bool {
if index == len(word) {
return true
}
if row < 0 || row >= rows || col < 0 || col >= cols ||
board[row][col] != word[index] {
return false
}
ret := false
temp := board[row][col]
board[row][col] = '#'
rowOffsets := []int{0, 1, 0, -1}
colOffsets := []int{1, 0, -1, 0}
for d := 0; d < 4; d++ {
ret = backtrack(row+rowOffsets[d], col+colOffsets[d], index+1)
if ret {
break
}
}
board[row][col] = temp
return ret
}
for row := 0; row < rows; row++ {
for col := 0; col < cols; col++ {
if board[row][col] == word[0] && backtrack(row, col, 0) {
return true
}
}
}
return false
}Explanation
Algorithm
1️⃣