矩阵中的路径【Java版】
矩阵中的路径
http://www.nowcoder.com/practice/2a49359695a544b8939c77358d29b7e6
【总体思路】(dfs+剪枝) x 多个起点
public class Solution { public boolean hasPath (char[][] matrix, String word) { boolean flag[][] = new boolean[matrix.length][matrix[0].length];//flag[][]数组,初始化为false,表示未经过的点 //一次初始化,之后共用 ==>是因为每次试探后,都会复原flag数组 for(int i = 0; i<= matrix.length-1; ++i){ for(int j=0; j<=matrix[0].length-1; ++j){//每行每列的全部格子作为起点,开始尝试 if(dfs(matrix, word, i, j, 0, flag)==true)return true;//如果找到一个,则完成任务+停止尝试,立即返回true } } return false;//全部失败,返回false //单个尝试的失败不会有任何返回 } public boolean dfs(char[][] matrix, String word, int i, int j, int count, boolean flag[][]){ if(0<=i && i<= matrix.length-1 && 0<=j && j<=matrix[0].length-1){//统一拦截==>【剪枝】 if(matrix[i][j] == word.charAt(count) && flag[i][j]==false){//匹配++ ++count;//也可以在后面都用count+1 if(count == word.length())return true;//完整匹配,则主动停止 //全文仅此一处、是true的源头 flag[i][j] = true;//【尝试改flag】(与下文还原flag对应) //下面递归结构类似4叉树的递归: if(dfs(matrix, word, i+1, j, count, flag) || dfs(matrix, word, i-1, j, count, flag) || dfs(matrix, word, i, j+1, count, flag) || dfs(matrix, word, i, j-1, count, flag) )return true;//这个return true是带有if的、起到传递true的作用,它不是源头 flag[i][j] = false;//【还原flag】//注意,平时传值都不需要"还原"(如count),而这里需要。 } //说明flag[][]数组,传的是指针(而不是提供副本),递归分支是共用一个的 } return false; } }//时间:O(rows*cols*3^word)//3是因为不能回头、减少一种路 //空间:1)flag空间 O(rows*cols) 2)栈空间O(word) //如果有类似线性匹配的KMP模式串的优化,会快一些
《剑指Offer-Java题解》 文章被收录于专栏
《剑指Offer-Java题解》