LeetCode刷题【212】单词搜索 II

给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，找出所有同时在二维网格和字典中出现的单词。

单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

示例 1：

输入：board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
输出：["eat","oath"]

示例 2：

输入：board = [["a","b"],["c","d"]], words = ["abcb"]
输出：[]

提示：

• m == board.length
• n == board[i].length
• 1 <= m, n <= 12
• board[i][j] 是一个小写英文字母
• 1 <= words.length <= 3 * 104
• 1 <= words[i].length <= 10
• words[i] 由小写英文字母组成
• words 中的所有字符串互不相同

题解，今日份的每日一题 9月16日

嗯，就回溯，没啥复杂的其实，

class Solution {

    char[][] board;
    int colLimit;
    int rowLimit;
    List<String> res;
    HashSet<String> wordsSet;
    boolean[][] visited;
    int[][] directions = new int[][]{{0,1},{1,0},{0,-1},{-1,0}};


    public List<String> findWords(char[][] board, String[] words) {
        this.board = board;
        colLimit = board[0].length-1;
        rowLimit = board.length-1;
        res = new ArrayList<>();
        visited = new boolean[board.length][board[0].length];
        wordsSet = new HashSet<>();
        HashMap<Character,List<int[]>> wordsBegin = new HashMap<>();
        for (String word : words) {
            wordsSet.add(word);
            if (!wordsBegin.containsKey(word.charAt(0))){
                wordsBegin.put(word.charAt(0),new ArrayList<>());
            }
        }
        for (int row = 0; row < board.length; row++) {
            for (int col = 0; col < board[row].length; col++) {
                if (wordsBegin.containsKey(board[row][col])){
                    wordsBegin.get(board[row][col]).add(new int[]{row,col});
                }
            }
        }

        wordsBegin.forEach((character, ints) -> {
            for (int[] anInt : ints) {
//                System.out.println(anInt[0]+" "+anInt[1]);
                List<Character> charArr = new ArrayList<>();
                charArr.add(board[anInt[0]][anInt[1]]);
                visited[anInt[0]][anInt[1]] = true;
                dfs(anInt, charArr);
                visited[anInt[0]][anInt[1]] = false;
            }
        });
        return res;
    }


    public void dfs(int[] position ,List<Character> charArr){
        if (charArr.size()==11){
            return;
        }
        char[] charArrCopy = new char[charArr.size()];
        for (int i = 0; i < charArr.size(); i++) {
            charArrCopy[i] = charArr.get(i);
        }
        String tmpStr = new String(charArrCopy);
//        System.out.println(new String(charArrCopy));
        if (wordsSet.size()>0 && wordsSet.contains(tmpStr)){
            res.add(tmpStr);
            wordsSet.remove(tmpStr);
        }
        for (int[] direction : directions) {
            int[] target = new int[]{position[0]+direction[0],position[1]+direction[1]};
            if ( target[0] < 0 || target[0] > rowLimit || target[1] < 0 || target[1] > colLimit || visited[target[0]][target[1]]){
                continue;
            }
            charArr.add(board[target[0]][target[1]]);
            visited[target[0]][target[1]] = true;
            dfs(target,charArr);
            charArr.remove(charArr.size()-1);
            visited[target[0]][target[1]] = false;
        }
    }
}

字典树的作法没太看懂，还要再看下研究下，然后这个回溯的，在回溯查找之前其实还可以再优化下，不应当把拼成的字符串到wordsSet中去查找，要查找的话必须要转成字符串，这样new 一个String对象的过程消耗不少，所以可以尝试，把wordsSet的结果转换成一个数据结构，可以快速查找到当前已经遍历的char数组是否能在这个结构中查找到。

这个回头再看下怎么弄，我设想的这个结构感觉可能就是类似字典树吧，我猜。