Playgrund: Word Search

Clase 46 de 52 • Curso de Algoritmos Avanzados: Grafos y Árboles

Clase anteriorSiguiente clase

John Eduard Meneses González

student•

My Solution!!

José Ramón García

student•

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

Carlos Hernandez

student•

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;
}