题解 | #牛群定位系统#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param board char字符型二维数组
     * @param words string字符串一维数组
     * @return string字符串一维数组
     */
    public static Set<String> result = new HashSet<>();
    public String[] findWords (char[][] board, String[] words) {
        // write code here
        Set<String> set = new HashSet<>();
        set.addAll(Arrays.asList(words));
        boolean[][] visited = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                search(board, visited, i, j, set, new StringBuffer());
            }
        }
        String[] strings = new String[result.size()];
        int index = 0;
        for (int i = 0; i < words.length; i++) {
            if (result.contains(words[i])) {
                strings[index++] = words[i];
            }
        }
        return strings;
    }

    public void search(char[][] board, boolean[][] visited, int i, int j,
                              Set<String> set, StringBuffer stringBuffer) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length ||
                visited[i][j]) {
            return;
        }
        if(set.contains(stringBuffer.toString()) && stringBuffer.toString().length()>0){
            result.add(stringBuffer.toString());
        }
        stringBuffer.append(board[i][j]);
        visited[i][j] = true;
        search(board, visited, i + 1, j, set, stringBuffer);
        search(board, visited, i - 1, j, set, stringBuffer);
        search(board, visited, i, j + 1, set, stringBuffer);
        search(board, visited, i, j - 1, set, stringBuffer);
        visited[i][j] = false;
        stringBuffer.deleteCharAt(stringBuffer.length() - 1);
    }
}

本题所考察的知识点是递归算法，所用编程语言是java。

往四个方向进行深度遍历，如果数组下标超过了数组合理下标位置则结束深度遍历