Question

How to search for a word in a grid of characters with Ruby

Answer 1

# Use a depth‑first search (DFS) from every cell that matches the first letter,
# exploring all valid directions until the full word is matched.

def dfs(grid, visited, r, c, word, index)
  return true if index == word.length

  rows = grid.length
  cols = grid[0].length

  return false if r < 0 || c < 0 || r >= rows || c >= cols
  return false if visited[r][c]
  return false if grid[r][c] != word[index]

  visited[r][c] = true

  found =
    dfs(grid, visited, r + 1, c, word, index + 1) ||
    dfs(grid, visited, r - 1, c, word, index + 1) ||
    dfs(grid, visited, r, c + 1, word, index + 1) ||
    dfs(grid, visited, r, c - 1, word, index + 1)

  visited[r][c] = false
  found
end

def word_exist(grid, word)
  rows = grid.length
  cols = grid[0].length

  visited = Array.new(rows) { Array.new(cols, false) }

  (0...rows).each do |r|
    (0...cols).each do |c|
      return true if dfs(grid, visited, r, c, word, 0)
    end
  end

  false
end

grid = [
  ['a', 'b', 'c', 'e'],
  ['s', 'f', 'c', 's'],
  ['a', 'd', 'e', 'e']
]

word = "see"

result = word_exist(grid, word)
puts result ? 1 : 0



#
# run:
# 
# 1
#

 

70+ SQL courses for beginners and professionals