递归的方法去做

这道题，最想不通的是为什么要给一个一维数组。给了一维数组需要转换二维数组，而且传参的时候，参数巨多，很容易搞错。总体思路是，采用一个bool类型的和原数组等大的数组来保存节点的访问状态，然后遍历原数组，当原数组中有一个元素的值和str的第一个元素相等时，就去继续判断，判断时，需要将matrix中元素的上下左右都判断一遍，如果相等，继续判断该相等元素的上下左右元素，很明显是一个递归的过程。那首先，为了降低问题复杂度，我们先将这个一维数组转换成二维数组来做，这样会清晰很多。代码如下：

public class Solution {
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        //首先找到第一个字母出现的位置
        if (matrix==null||matrix.length==0||matrix.length<str.length)
            return false;
        char[][] mat=new char[rows][cols];
        int start=0;
        for (int i=0;i<rows;++i){
            for (int j=0;j<cols;++j)
                mat[i][j]=matrix[start++];
        }
        for (int i=0;i<rows;++i){
            for (int j=0;j<cols;++j){
                if (mat[i][j]==str[0]){
                    boolean[][] flag=new boolean[rows][cols];
                    flag[i][j]=true;
                    if (hasPath(mat,flag,str,i,j,1))
                        return true;
                    else
                        flag[pos]=false;
                }
            }
        }
        return false;
    }

    public boolean hasPath(char[][] matrix,boolean[][] flag,char[] str,int startRow,int startCol,int curPos){
        //计算得到当前位置上下左右的位置
        if (curPos==str.length)
            return true;
        //上
        int newPos;
        if (startRow>0){
            newPos=startRow-1;
            if (dealData(matrix,flag,str,newPos,startCol,curPos))
                return true;
        }
        //下
        if (startRow<matrix.length-1){
            newPos=startRow+1;
            if (dealData(matrix,flag,str,newPos,startCol,curPos))
                return true;
        }
        //左
        if (startCol>0){
            newPos=startCol-1;
            if (dealData(matrix,flag,str,startRow,newPos,curPos))
                return true;
        }
        //右
        if (startCol<matrix[0].length-1){
            newPos=startCol+1;
            if (dealData(matrix,flag,str,startRow,newPos,curPos))
                return true;
        }
        return false;
    }

    public boolean dealData(char[][] matrix,boolean[][] flag,char[] str,int startRow,int startCol,int curPos){
        if (matrix[startRow][startCol]==str[curPos]&&!flag[startRow][startCol]){
            flag[startRow][startCol]=true;
            if (hasPath(matrix,flag,str,startRow,startCol,curPos+1))
                return true;
            else
                flag[startRow][startCol]=false;
        }
        return false;
    }
}

有了二维数组的基础，那我们再将一维数组转换成二维数组，就可以了（不得不说，用一维数组变量真多的。。。代码好丑）一维数组的代码如下:

public class Solution {
    public int rows;
    public int cols;
    public int rowCount;
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        if (matrix==null||matrix.length==0||matrix.length<str.length)
            return false;
        //首先找到第一个字母出现的位置
        this.rows=rows;
        this.cols=cols;
        int rowNum=matrix.length/rows;
        this.rowCount=rowNum;
        for (int i=0;i<rows;++i){
            for (int j=0;j<cols;++j){
                int pos=rowNum*i+j;
                if (matrix[pos]==str[0]){
                    boolean[] flag=new boolean[matrix.length];
                    flag[pos]=true;
                    if (hasPath(matrix,flag,str,i,j,1))
                        return true;
                    else
                        flag[pos]=false;
                }
            }
        }
        return false;
    }

    public boolean hasPath(char[] matrix,boolean[] flag,char[] str,int startRow,int startCol,int curPos){
        //计算得到当前位置上下左右的位置
        if (curPos==str.length)
            return true;
        //上
        int newPos;
        if (startRow>0){
            newPos=startRow-1;
            if (dealData(matrix,flag,str,newPos,startCol,curPos))
                return true;
        }
        //下
        if (startRow<this.rows-1){
            newPos=startRow+1;
            if (dealData(matrix,flag,str,newPos,startCol,curPos))
                return true;
        }
        //左
        if (startCol>0){
            newPos=startCol-1;
            if (dealData(matrix,flag,str,startRow,newPos,curPos))
                return true;
        }
        //右
        if (startCol<this.cols-1){
            newPos=startCol+1;
            if (dealData(matrix,flag,str,startRow,newPos,curPos))
                return true;
        }
        return false;
    }

    public boolean dealData(char[] matrix,boolean[] flag,char[] str,int startRow,int startCol,int curPos){
        int pos=startRow*this.rowCount+startCol;
        if (matrix[pos]==str[curPos]&&!flag[pos]){
            flag[pos]=true;
            if (hasPath(matrix,flag,str,startRow,startCol,curPos+1))
                return true;
            else
                flag[pos]=false;
        }
        return false;
    }
}

上面的代码中，最最重要的是，当条件不符合时，要将flag恢复为false，以免影响后面的判断