79. Word Search
給定一個 m x n 的字符網格 board 和一個字符串 word，如果 word 存在於網格中，則返回 true。
這個單詞可以由順序相鄰的單元格中的字母構成，其中相鄰單元格是水平或垂直相鄰的。相同的字母單元格不能被多次使用。
範例 1：
輸入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" 輸出：true
Python
from typing import List
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
# Define the dimensions of the board
rows, cols = len(board), len(board[0])
# Helper function to perform DFS
def dfs(r, c, i):
# If all characters are checked
if i == len(word):
return True
# If out of bounds or not matching the character or already visited
if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[i]:
return False
# Mark the cell as visited by storing the current character and replacing it
temp = board[r][c]
board[r][c] = '#'
# Explore in all four directions
found = (
dfs(r + 1, c, i + 1) or
dfs(r - 1, c, i + 1) or
dfs(r, c + 1, i + 1) or
dfs(r, c - 1, i + 1)
)
# Restore the cell's original character
board[r][c] = temp
return found
# Start from each cell
for r in range(rows):
for c in range(cols):
if dfs(r, c, 0):
return True
return False
16.48MB, 2987ms
C++
#include <vector>
#include <string>
class Solution {
public:
bool exist(std::vector<std::vector<char>>& board, std::string word) {
int rows = board.size();
int cols = board[0].size();
for (int r = 0; r < rows; ++r) {
for (int c = 0; c < cols; ++c) {
if (dfs(board, word, r, c, 0)) {
return true;
}
}
}
return false;
}
private:
bool dfs(std::vector<std::vector<char>>& board, const std::string& word, int r,
int c, int index) {
if (index == word.size()) {
return true;
}
if (r < 0 || r >= board.size() || c < 0 || c >= board[0].size() ||
board[r][c] != word[index]) {
return false;
}
char temp = board[r][c];
board[r][c] = '#'; // Mark the cell as visited
bool found = dfs(board, word, r + 1, c, index + 1) ||
dfs(board, word, r - 1, c, index + 1) ||
dfs(board, word, r, c + 1, index + 1) ||
dfs(board, word, r, c - 1, index + 1);
board[r][c] = temp; // Restore the cell's original value
return found;
}
};
9.36MB, 202ms
Javascript
/**
* @param {character[][]} board
* @param {string} word
* @return {boolean}
*/
var exist = function(board, word) {
const rows = board.length;
const cols = board[0].length;
const dfs = (r, c, index) => {
// If all characters are checked
if (index === word.length) {
return true;
}
// If out of bounds or not matching the character or already visited
if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== word[index]) {
return false;
}
// Mark the cell as visited by storing the current character and replacing it
const temp = board[r][c];
board[r][c] = '#';
// Explore in all four directions
const found = (
dfs(r + 1, c, index + 1) ||
dfs(r - 1, c, index + 1) ||
dfs(r, c + 1, index + 1) ||
dfs(r, c - 1, index + 1)
);
// Restore the cell's original character
board[r][c] = temp;
return found;
};
// Start from each cell
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (dfs(r, c, 0)) {
return true;
}
}
}
return false;
};
48.86MB, 356ms
