剑指 Offer 12. 矩阵中的路径

❤DFS+合理剪枝

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。

[[“a”,”b”,”c”,”e”], [“s”,”f”,”c”,”s”], [“a”,”d”,”e”,”e”]]

但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

思路

显然为典型的矩阵搜索问题，可使用DFS+剪枝解决

  • DFS:每次都朝向四个方向搜索，以此类推

  • 剪枝：当该路径无效or该路径已遍历过时，立即返回，即可行性剪枝

    算法

  • 递归参数：当前矩阵索引(i,j)和对应字符串索引idx

  • 终止条件：
    1. 返回false:越界或当前字符不匹配或当前字符已访问
    2. 返回true:字符串word已全部匹配
  • 递归变化：
    1. 标记当前元素：暂存board[i][j],并将其board[i][j]置为'\0'
    2. 递归搜索下一个:往四个方向开启递归
    3. 还原当前元素：board[i][j]

      实现

      ```cpp vector> direction={{0,-1},{0,1},{-1,0},{1,0}}; bool dfs(vector>& board,int i,int j,int m,int n, const string& word,int idx,int wSize){ if(board[i][j]!=word[idx]) return false; if(idx==wSize-1) return true; char tmp=board[i][j]; board[i][j]=’\0’; for(auto d:direction){ int newi=i+d.first,newj=j+d.second; if(newi>-1 && newi-1 && newj<n) {
      1.   if(dfs(board,newi,newj,m,n,word,idx+1,wSize)){
      2.       return true;
      3.   }
      } } board[i][j]=tmp; return false; }

```

复杂度分析

  • 时间复杂度：

最差的情况下，需要遍历矩阵中长度为K的所有方案。

设字符串长度为K，则搜索时每次可选择的方向为上下左右，舍弃回头的方向，则每次有三个方向可选择。 因此方案复杂度为O(3)

O(3MN)

  • 空间复杂度：

搜索过程中，搜索深度不会超过K，则系统因函数调用累计使用的栈空间用O(K)。