JavaScript solution with extra space


  • 0
    Y
    function makeGrid(grid, cellFactory) {
      const numRows = grid.length
      const numCols = grid[0].length
      const attempts = Array(numRows).fill().map(() => Array(numCols).fill())
      for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
          attempts[i][j] = cellFactory(i, j)
        }
      }
      return attempts
    }
    
    function hasWord(grid, word) {
      const numRows = grid.length
      const numCols = grid[0].length
      const attempts = makeGrid(grid, () => new Set())
      const isInWord = makeGrid(grid, () => false)
      for (let i = 0; i < numRows; i++) {
        for (let j = 0; j < numCols; j++) {
          if (hasWordHelper(grid, word, 0, i, j, attempts, isInWord)) {
            return true
          }
        }
      }
      return false
    }
    
    function isValidPosition(grid, rowIndex, colIndex) {
      const numRows = grid.length
      const numCols = grid[0].length
      return Math.min(rowIndex, colIndex) >= 0 && rowIndex < numRows && colIndex < numCols
    }
    
    function hasWordHelper(grid, word, index, rowIndex, colIndex, attempts, isInWord) {
      if (index === word.length) {
        return true
      } else if (
        !isValidPosition(grid, rowIndex, colIndex) ||
        attempts[rowIndex][colIndex].has(index) ||
        isInWord[rowIndex][colIndex]
      ) {
        return false
      }
      if (grid[rowIndex][colIndex] === word.charAt(index)) {
        isInWord[rowIndex][colIndex] = true
        if (
          hasWordHelper(grid, word, index + 1, rowIndex + 1, colIndex, attempts, isInWord) ||
          hasWordHelper(grid, word, index + 1, rowIndex - 1, colIndex, attempts, isInWord) ||
          hasWordHelper(grid, word, index + 1, rowIndex, colIndex + 1, attempts, isInWord) ||
          hasWordHelper(grid, word, index + 1, rowIndex, colIndex - 1, attempts, isInWord)
        ) {
          return true
        }
      } else {
        attempts[rowIndex][colIndex].add(index)
      }
      // cannot expand partial candidate
      isInWord[rowIndex][colIndex] = false
      return false
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.