题解 | #牛群定位系统#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param board char字符型二维数组
     * @param words string字符串一维数组
     * @return string字符串一维数组
     */
    public String[] findWords (char[][] board, String[] words) {
        // write code here
        ArrayList<String> array = new ArrayList<String>();
        for (int x = 0; x < words.length; x++) {
            if (findWords(board, words[x], 0, 0, 0)) {
                array.add(words[x]);
            }
        }
        int len = array.size();
        String[] res = new String[len];
        for (int i = 0; i < len; i++) {
            res[i] = array.get(i);
        }
        return res;
    }
    public boolean findWords(char[][] board, String word, int i, int j, int index) {
        if (i < 0  || i >= board.length || j < 0 || j >= board[i].length) {
            return index == word.length() ? true : false;
        }
        if (index == word.length()) {
            return true;
        }

        if (board[i][j] == word.charAt(index)) {
            // 做出选择
            char c = board[i][j];
            board[i][j] = '#';
            // 四个方向寻找
            boolean up = findWords(board, word, i + 1, j, index + 1);
            boolean down = findWords(board, word, i - 1, j, index + 1);
            boolean right = findWords(board, word, i, j + 1, index + 1);
            boolean left = findWords(board, word, i, j - 1, index + 1);
            // 撤销选择
            board[i][j] = c;
            return up || down || left || right;
        } else if (board[i][j] == '#') {
            return false;
        }
        if (index != 0) {
            // 说明已经使用过相邻字符了，如果还没有找到，则说明不存在
            return false;
        }
        // 下和右方向寻找
        boolean down = findWords(board, word, i + 1, j, index);
        boolean right = findWords(board, word, i, j + 1, index);
        return down || right;
    }
}

判断二维数组中是否存在字符串words[x]，如果存在就添加到最后结果中，如果不存在就继续向下找

找四个方向会造成栈溢出，所以从左上角指遍历右边和下边两个方向防止无限递归造成栈溢出。