Clase 46 de 52 • Curso de Algoritmos Avanzados: Grafos y Árboles
Contenido del curso
John Eduard Meneses González
José Ramón García
Carlos Hernandez
My Solution!!
Mi solución en Python
def word_exist(matrix, word): rows, cols = len(matrix), len(matrix[0]) moves = [(-1, 0), (1, 0), (0, -1), (0, 1)] def in_matriz(x,y): return 0 <= x < rows and 0 <= y < cols def dfs(x, y, level, visited): if level == len(word) - 1: return True visited.add((x, y)) for i, j in moves: nx, ny = x + i, y + j if( in_matriz(nx,ny) and (nx, ny) not in visited and matrix[nx][ny] == word[level + 1] ): if dfs(nx, ny, level + 1, visited): return True visited.remove((x,y)) return False for i in range(rows): for j in range(cols): if matrix[i][j] == word[0]: if dfs(i,j, 0, set()): return True return False
Mi solución:
function verifyWordFromBoard(i, j, word, board, currentWord, matches, visitedSpots) { if (i < 0 || i >= board.length) return; if (j < 0 || j >= board[i].length) return; if (!word.includes(currentWord)) return; if (word === currentWord) return matches.push(currentWord); if (visitedSpots.find((spot) => spot.i === i && spot.j === j)) return; visitedSpots.push({ i, j }); verifyWordFromBoard(i - 1, j, word, board, currentWord + board[i][j], matches, visitedSpots); verifyWordFromBoard(i, j + 1, word, board, currentWord + board[i][j], matches, visitedSpots); verifyWordFromBoard(i + 1, j, word, board, currentWord + board[i][j], matches, visitedSpots); verifyWordFromBoard(i, j - 1, word, board, currentWord + board[i][j], matches, visitedSpots); } export function wordExist(board, word) { let visitedSpots = []; for (let i = 0; i < board.length; i++) { const row = board[i]; for (let j = 0; j < row.length; j++) { const letter = row[j]; let matches = []; if (letter === word[0]) { verifyWordFromBoard(i, j, word, board, '', matches, visitedSpots); } if (matches.length > 0) return true; } } return false; }
