79. 单词搜索

题意：

解题思路：

思路：DFS深度优先搜索[回溯]；
时间复杂度：(m * n) ^ 2

PHP代码实现：

class Solution {
    /**
     * @param String[][] $board
     * @param String $word
     * @return Boolean
     */
    function exist($board, $word) {
        $x = count($board);
        $y = count($board[0]);
        for ($i = 0; $i < $x; $i++) {
            for ($j = 0; $j < $y; $j++) {
                $res = $this->do($board, $i, $j, $word, 0);
                if ($res) return true;    
            }
        }
        return false;
    }
    function do($board, $i, $j, $word, $start) {
        if ($start >= strlen($word)) return true;
        if ($board[$i][$j] != $word[$start] || $i < 0 
            || $i >= count($board) || $j < 0 || $j >= count($board[0])) {
                return false;
            }
        $c = $word[$start];
        //abcb
        $board[$i][$j] = "#";// 避免该位重复使用
        $res = ($this->do($board, $i + 1, $j, $word, $start + 1) || 
            $this->do($board, $i - 1, $j, $word, $start + 1) ||
            $this->do($board, $i, $j + 1, $word, $start + 1) ||
            $this->do($board, $i, $j - 1, $word, $start + 1)
        );
        $board[$i][$j] = $c;// 如果都不通，则回溯上一状态
        return $res;
    }
}

GO代码实现：

func exist(board [][]byte, word string) bool {
    m := len(board)
    n := len(board[0])
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if backtrace(board, word, i, j, 0) {
                return true
            }
        }
    }
    return false
}
func backtrace(board [][]byte, word string, i, j, k int) bool {
    if k == len(word) {
        return true
    }
    if i < 0 || j < 0 || i == len(board) || j == len(board[i]) {
        return false
    }
    if board[i][j] != word[k] {
        return false
    }
    tmp := board[i][j]
    // 重置为空，避免回溯时重复使用
    board[i][j] = byte(' ')
    // 向上，向下，向左，向右
    if backtrace(board, word, i - 1, j, k + 1) {
        return true
    }
    if backtrace(board, word, i + 1, j, k + 1) {
        return true
    }
    if backtrace(board, word, i, j - 1, k + 1) {
        return true
    }
    if backtrace(board, word, i, j + 1, k + 1) {
        return true
    }
    board[i][j] = tmp
    return false
}