🌕🌕 212. 单词搜索 II

难度: 🌕🌕

问题描述

---

解法 1 - 单纯回溯[超时]

class Solution {
    List<String> res = new ArrayList<>();
    HashSet<String> set = new HashSet<>();
    public List<String> findWords(char[][] board, String[] words) {
        // 思路：
        // 回溯 - 依次遍历 words 所有单词，判断是否存在于 board 中
        int row = board.length;
        int col = board[0].length;
        for(String cur : words) {
            char first = cur.charAt(0);
            for(int i = 0; i < row; i ++) {
                for(int j = 0; j < col; j ++) {
                    if(board[i][j] == first) {
                        // 如果采用 int[] 作为参数，那么每次的 int[] 都是一个新对象，永远不相同
                        // 通过染色，判断路径是否重复
                        mySol(board, row, col, cur, 0, i, j);
                    }
                }
            }
        }
        return res;
    }

    private void mySol(char[][] board, int row, int col, String cur, int index, int i, int j) {
        // 递归终止条件
        if(index == cur.length()) {
            if(!set.contains(cur)) {
                res.add(cur);
                set.add(cur);
            }
            return;
        }
        if(i < 0 || j < 0 || i >= row || j >= col) {
            return;
        }
        if(board[i][j] != cur.charAt(index)) {
            return;
        }

        char store = board[i][j];
        board[i][j] = '#';
        mySol(board, row, col, cur, index + 1, i + 1, j);
        mySol(board, row, col, cur, index + 1, i - 1, j);
        mySol(board, row, col, cur, index + 1, i, j - 1);
        mySol(board, row, col, cur, index + 1, i, j + 1);
        board[i][j] = store;
    }
}

---

---

解法 2 - 字典树 + 回溯

class Solution {
    Node root;
    int row;
    int col;
    List<String> res = new ArrayList<>();
    public List<String> findWords(char[][] board, String[] words) {
        // 思路：
        // 遍历单词，然后查找 board 进行回溯，这种思路超时，需要优化
        // 改为:
        // 构造 26 叉树，存放所有单词
        // 遍历 board，遇到当前存在子树 == board[i][j] 则说明可以继续往下搜索，直到遍历完成
        // 此外，匹配到单词后，为防止其他节点出发也能形成该单词，因此可以将其从前缀树中修改 end 标志位，那么之后
        // 其他单词比不会匹配到，从而达到去重目的
        root = new Node('a');
        for(String str: words) {
            insert(str);
        }

        // 遍历 board 所有位置
        row = board.length;
        col = board[0].length;
        for(int i = 0; i < row; i ++) {
            for(int j = 0; j < col; j ++) {
                mySol(board, i, j, root);
            }
        }
        return res;
    }

    private void mySol(char[][] board, int i, int j, Node cur) {
        // 递归终止条件
        if(i < 0 || j < 0 || i >= row || j >= col) {
            return;
        }
        if(cur == null) {
            return;
        }
        if(board[i][j] == '#') {
            return; 
        }
        char c = board[i][j];
        int index = c - 'a';
        // System.out.println(i + "  " + j  + "  " + c + "  " + cur.s);
        if(cur.child[index] != null) {
            if(cur.child[index].end) {
                // 说明匹配到前缀树中某个单词的结尾了，添加到结果集中
                res.add(cur.child[index].s);
                cur.child[index].end = false; // 修改标志位，去重
            }
            board[i][j] = '#';
            mySol(board, i + 1, j, cur.child[index]);
            mySol(board, i - 1, j, cur.child[index]);
            mySol(board, i, j - 1, cur.child[index]);
            mySol(board, i, j + 1, cur.child[index]);
            board[i][j] = c;
            
        }
    }

    private void insert(String str) {
        Node cur = root;
        int len = str.length();
        for(int i = 0; i < len; i ++) {
            char c = str.charAt(i);
            int index = c - 'a';
            if(cur.child[index] == null) {
                cur.child[index] = new Node(c);
                cur.child[index].s = cur.s + String.valueOf(c);
            }
            cur = cur.child[index];
        }
        cur.end = true;
    }
}

class Node {
    char val;
    boolean end;
    Node[] child;
    String s; // 从根节点到当前节点，字符串
    public Node(char val) {
        this.val = val;
        this.end = false;
        this.child = new Node[26];
        s = "";
    }
}

---

输出