1. 概述

给定一个二维网格和一个单词，找出该单词是否存在于网格中。 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

board =

[

[‘A’,’B’,’C’,’E’],

[‘S’,’F’,’C’,’S’],

[‘A’,’D’,’E’,’E’]

]

给定 word = “ABCCED”, 返回 true

给定 word = “SEE”, 返回 true

给定 word = “ABCB”, 返回 false

2. 解题

<?php
// TODO
class Solution {
    /**
     * @param String[][] $board
     * @param String $word
     * @return Boolean
     */
    public function exist($board, $word) {
        for ($i = 0; $i < count($board); $i++) {
            for ($j = 0; $j < count($board[0]); $j++) {
                $ret = $this->do($board, $i, $j, $word, 0);
                if ($ret) {
                    return true;
                }
            }
        }
        return false;
    }
    /**
     * @param array $board      需要被搜索的数组
     * @param int $row          需要被搜索的行
     * @param int $col          需要被搜索的列
     * @param string $word      目标字符串
     * @param int $needCharKey  目标字符下表
     * @return bool
     */
    private function do(array &$board, int $row, int $col, string $word, int $needCharKey) {
        // 边界检查
        if (($row < 0) || ($col < 0) || ($row >= count($board)) || ($col >= count($board[0]))) {
            return false;
        }
        // 字符检查是否一致
        if ($board[$row][$col] != $word[$needCharKey]) {
            return false;
        }
        // 是否已经检查完目标字符串
        if ($needCharKey == strlen($word) - 1) {
            return true;
        }
        // 将搜索过数组元素改为 # , 等待回溯恢复
        $tmp = $board[$row][$col];
        $board[$row][$col] = '#';
        // 继续递归搜索：上，左，下，右
        $nextNextCharKey = $needCharKey + 1;
        if ($this->do($board, $row - 1, $col, $word, $nextNextCharKey)
            || $this->do($board, $row, $col - 1, $word, $nextNextCharKey)
            || $this->do($board, $row + 1, $col, $word, $nextNextCharKey)
            || $this->do($board, $row, $col + 1, $word, $nextNextCharKey)) {
            return true;
        }
        // 回溯需要将原来的字符改回
        $board[$col][$row] = $tmp;
        return false;
    }
}
$board = [
    ['A','B','C','E'],
    ['S','F','C','S'],
    ['A','D','E','E']
];
// $word = "ABCCED";
$word = "SEE";
// $word = "ABCB";
$cls = new Solution();
$ret = $cls->exist($board, $word);
var_dump($ret);