题解 | #牛群定位系统#

知识点：回溯

这道题本身也属于一个普通的回溯寻找路径的问题，但是这道题的难点在于细节的处理上。题目要求找出符合要求的字符串，这就不同于普通的回溯，要找出所有的字符串，故我们使用Set集合来存储符合条件的字符串即可。还有一个点在于输出顺序并非是普通的按字典序排列，题目要求输出顺序为数组中的出现顺序，故我们需要使用一个Map来对数组中的字符串赋予权重，以便后续对结果的排序。

Java题解如下

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param board char字符型二维数组 
     * @param words string字符串一维数组 
     * @return string字符串一维数组
     */
    private int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    private Set<String> res = new HashSet<>();
    private int m, n;
    private char[][] board;
    private boolean[][] visited;
    
    public String[] findWords (char[][] board, String[] words) {
        // write code here
        m = board.length;
        n = board[0].length;
        this.board = board;
        visited = new boolean[m][n];
        for(String word: words) {
            for(int i = 0; i < m; i++) {
                for(int j = 0; j < n; j++) {
                    backTracking(word, 0, i, j);
                }
            }
        }
        Map<String, Integer> map = new HashMap<>();
        for(int i = 0; i < words.length; i++) {
            map.put(words[i], i);
        }
        List list = new ArrayList<>(res);
        Collections.sort(list, (o1, o2) -> (map.get(o1) - map.get(o2)));
        String[] ans = new String[list.size()];
        for(int i = 0; i < res.size(); i++) {
            ans[i] = String.valueOf(list.get(i));
        }
        return ans;
    }

    private void backTracking(String word, int index, int x, int y) {
        if(x < 0 || x >= m || y < 0 || y >= n || visited[x][y] || word.charAt(index) != board[x][y]) {
            return;
        }
        if(index == word.length() - 1) {
            res.add(word);
            return;
        }
        visited[x][y] = true;
        for(int[] dir: dirs) {
            backTracking(word, index + 1, x + dir[0], y + dir[1]);
        }
        visited[x][y] = false;
    }
}