Leetcode基础刷题之PHP解析(79. Word Search)

2019-6-14 星期五 开始吧

上一题链接Leetcode基础刷题之PHP解析(78. Subsets)

题目描述

给定一个二维数组，其实可以理解成网格，然后让我们再网格中寻找是否存在指定的元素，当然它的寻找方式有点特殊，你只能在你需要匹配的当前字符串的上下左右的位置找下一个匹配的字符串，如果匹配那么继续找，就可以理解成下象棋一下 ，小兵的下一步只能左右上下?.emmmm打脸了，小兵不能后退。

题目分析

所以我们需要遍历两层，第一层可以理解成行，第二层是列，先找到第一个和给定字符串第一个字母相等的位置。确定开始的位置，然后开始递归的调用，递归里面，因为是一个个去匹配的，所以我们需要知道当前匹配的是哪个字符串，另外一个当前匹配完的数不能再次利用，所以需要标记。就是因为需要考虑的情况太多，所以这道题显得很麻烦,具体看php代码。

 
    /**
     * @param String[][] $board
     * @param String $word
     * @return Boolean
     */
    function exist($board, $word) {
        if(empty($board) || empty($board[0])) return false;
        
        for($i=0;$i<count($board);$i++){
            for($j=0;$j<count($board[0]);$j++){
                if($this->helper($board,$word,0,$i,$j,$visited[$i][$j])) return true;
            
            }
        }
        return false;
    }
    
    function helper($board,$word,$index,$row,$col, &$visited){
        //找到匹配的单词
        if($index==strlen($word)) return true; 
        
        //边界的处判断以及 当前行列对应值是否和匹配的当前位置字符串相等
       if($row<0 || $col <0 || $row >= count($board) || $col>=count($board[0]) 
          || $visited[$row][$col] || $board[$row][$col] != $word[$index] ) return false;
       
        $visited[$row][$col]=true;
        //递归调用下一个需要匹配的四个方向行列位置的变化
        if($this->helper($board,$word,$index+1,$row-1,$col,$visited)  || $this->helper($board,$word,$index+1,$row+1,$col,$visited) 
           || $this->helper($board,$word,$index+1,$row,$col-1,$visited) || $this->helper($board,$word,$index+1,$row,$col+1,$visited)) return true;
        
        //此路不通爷回退
        $visited[$row][$col]=false;
    
        return false;
       
    }

Github整理地址:https://github.com/wuqinqiang/leetcode-php