-
Notifications
You must be signed in to change notification settings - Fork 1
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
79. Word Search #265
Labels
Comments
Solution
/**
* @param {character[][]} board
* @param {string} word
* @return {boolean}
*/
var exist = function(board, word) {
const visited = '*';
const direction = [-1, 0, 1, 0, -1];
let result = false;
for (let i = 0; i < board.length; i++) {
for (let j = 0; j < board[0].length; j++) {
dfs([i, j], 0);
}
}
return result;
function dfs([x, y], wordIndex) {
const currentVal = board[x][y];
if (result) {
return;
}
if (currentVal === visited || currentVal !== word[wordIndex]) {
return;
}
if (wordIndex === word.length - 1) {
result = true
return;
}
board[x][y] = visited;
for (let i = 0; i < 4; i++) {
const directionX = x + direction[i];
const directionY = y + direction[i + 1];
if (
directionX >= 0 && directionX < board.length
&& directionY >= 0 && directionY < board[0].length
) {
dfs([directionX, directionY], wordIndex + 1);
}
}
board[x][y] = currentVal;
}
};
function exist(board: string[][], word: string): boolean {
const visited = '*';
const direction = [-1, 0, 1, 0, -1];
let result = false;
for (let i = 0; i < board.length; i++) {
for (let j = 0; j < board[0].length; j++) {
dfs([i, j], 0);
}
}
return result;
function dfs([x, y]: [number, number], wordIndex: number) {
const currentVal = board[x][y];
if (result) {
return;
}
if (currentVal === visited || currentVal !== word[wordIndex]) {
return;
}
if (wordIndex === word.length - 1) {
result = true
return;
}
board[x][y] = visited;
for (let i = 0; i < 4; i++) {
const directionX = x + direction[i];
const directionY = y + direction[i + 1];
if (
directionX >= 0 && directionX < board.length
&& directionY >= 0 && directionY < board[0].length
) {
dfs([directionX, directionY], wordIndex + 1);
}
}
board[x][y] = currentVal;
}
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
79. Word Search
给定一个二维网格和一个单词,找出该单词是否存在于网格中。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
Example
Note
board
和word
中只包含大写和小写英文字母。1 <= board.length <= 200
1 <= board[i].length <= 200
1 <= word.length <= 10^3
The text was updated successfully, but these errors were encountered: