思路

1. 找到字符串头节点字符，然后使用栈保存后续的每个节点
2. 每个节点的查找方向有三个（来的方向需要去除），依次递归便利这三个方向，查看是否能找到完整字符串

class Solution {

    // 通过栈保存元素遍历顺序
    Stack<Word> stack = new Stack();
    // 判断是否存在
    public boolean exist(char[][] board, String word) {
         char[] chs = word.toCharArray();
        if (chs.length == 0 || board.length == 0 || board[0].length == 0) return false;
        int rows = board.length;
        int cols = board[0].length;
        if (word.length() > rows*cols) return false;

        // 找到首字母
        List<Word> frstWord = new ArrayList();
        for(int i = 0; i <  rows; i ++) {
            for(int j = 0; j < cols; j++) {
                if (board[i][j] == chs[0]) {
                    frstWord.add(new Word(chs[0], i, j));
                }
            }
        }

        if (frstWord.size() == 0) return false;

        for(Word fw : frstWord) {
            // 从首字母出发找到了对应的所有字母，返回查找成功
            stack.push(fw);
	    // 递归判断每个首字母出发是否能找到字符串
            if (scanWord(board, fw, chs, 1, 0))
                return true;
        }

        return false;

    }
    // 找到对应字符串
    boolean scanWord(char[][] board, Word word, char[] chs, int index, int dt) {
        if (word.dt >= 5) return false;
        if (index >= chs.length) return true;
	// word.dt 表示字符方向，dt表示来的方向
        if (word.dt == 1 && dt != 3) {

            // 向上的时候必须不能在row==0的位置
            if (word.row > 0) {
                if (board[word.row - 1][word.col] == chs[index]) {
                    // 寻找下个元素
                    Word next = new Word(chs[index], word.row - 1, word.col);
		    // 需要判断栈中是否存在元素，避免回环查找到元素
                    if (!stack.contains(next)) {
                    stack.push(next);
                    if(scanWord(board, next, chs, index + 1, 1)) {
                        // 递归查找下一个元素
                        return true;
                    }}
                }
            }
        }
        word.dt ++;

        if (word.dt == 2 && dt != 4) {
            // 向右的时候必须不能在col==board[0].length的位置
            if (word.col < board[0].length - 1) {
                if (board[word.row][word.col + 1] == chs[index]) {
                    // 寻找下个元素
                    Word next = new Word(chs[index], word.row, word.col + 1);
                    if (!stack.contains(next)) {
                    stack.push(next);
                    if(scanWord(board, next, chs, index + 1,2)) {
                        // 递归查找下一个元素
                        return true;
                    }}
                }
            }
        }
        word.dt ++;

        if (word.dt == 3 && dt != 1) {
            // 向下的时候必须不能在row==board.length - 1的位置
            if (word.row < board.length - 1) {
                if (board[word.row + 1][word.col] == chs[index]) {
                    // 寻找下个元素
                    Word next = new Word(chs[index], word.row + 1, word.col);
                    if (!stack.contains(next)) {
                    stack.push(next);
                    if(scanWord(board, next, chs, index + 1,3)) {
                        // 递归查找下一个元素
                        return true;
                    }}
                }
            }
        }
        word.dt ++;

        if (word.dt == 4 && dt != 2) {
            // 向左的时候必须不能在col == 0的位置
            if (word.col > 0) {
                if (board[word.row][word.col - 1] == chs[index]) {
                    // 寻找下个元素
                    Word next = new Word(chs[index], word.row, word.col - 1);
                    if (!stack.contains(next)) {
                    stack.push(next);
                    if(scanWord(board, next, chs, index + 1,4)) {
                        // 递归查找下一个元素
                        return true;
                    }}
                }
            }
        }
        word.dt ++;

        // 该元素出栈
        stack.pop();

        return false;
        
    }

    
}

class Word {
    public char ch;
    // 方向 1-4 上右下左
    public int dt;
    // 行 0～board.length
    public int row;
    // 列 0~board[0].length
    public int col;

    Word(char c,int row,int col) {
        this.ch = c;
        this.dt = 1;
        this.row = row;
        this.col = col;
    }

    @Override
    public boolean equals(Object obj) {
        Word word = (Word)obj;
        return this.ch == word.ch && this.row == word.row && this.col == word.col;
    }
}

思路2

1. 也是每个元素四个方向的便利，这里只需要检查是否存在check(i,j,chars,index) == true即可，如果存在则返回true
2. 为了避免查询已经确认存在的位置，增加一个位置矩阵

// 回溯

Q.E.D.