Question

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

Answer 1

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

function dfs(&$grid, &$visited, $r, $c, $word, $index) {
    if ($index === strlen($word)) {
        return true;
    }

    $rows = count($grid);
    $cols = count($grid[0]);

    if ($r < 0 || $c < 0 || $r >= $rows || $c >= $cols) {
        return false;
    }

    if ($visited[$r][$c]) {
        return false;
    }

    if ($grid[$r][$c] !== $word[$index]) {
        return false;
    }

    $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;
    return $found;
}

function wordExist($grid, $word) {
    $rows = count($grid);
    $cols = count($grid[0]);

    $visited = array_fill(0, $rows, array_fill(0, $cols, false));

    for ($r = 0; $r < $rows; $r++) {
        for ($c = 0; $c < $cols; $c++) {
            if (dfs($grid, $visited, $r, $c, $word, 0)) {
                return true;
            }
        }
    }

    return false;
}

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

$word = "see";

$result = wordExist($grid, $word);

echo $result ? 1 : 0;


/*
run:

1

*/

 

70+ SQL courses for beginners and professionals