212. Word Search II[Hard]

212. Word Search II

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
Constraints:

• m == board.length
• n == board[i].length
• 1 <= m, n <= 12
• board[i][j] is a lowercase English letter.
• 1 <= words.length <= 3 * 104
• 1 <= words[i].length <= 10
• words[i] consists of lowercase English letters.
• All the strings of words are unique.

Example

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

思路

先把字典里的String都转换成前缀树，接下来就是去遍历数组中的每一个点，看是否能匹配上前缀树，注意保存路径就用boolean的二维数组来存就行，不要用HashSet之类的数据结构保存，会超时

题解

   class TrieNode {
        HashMap<Character, TrieNode> node = new HashMap<>();
        boolean isEnd;
    }

    TrieNode root = new TrieNode();

    public List<String> findWords(char[][] board, String[] words) {
        buildTrieNode(words);
        TrieNode cur = root;
        boolean[][] path = new boolean[board.length][board[0].length];
        List<String> res = new ArrayList<>();

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                dfsFindWord(i, j, board, path, cur, "", res);
            }
        }
        return res;
    }

    public void dfsFindWord(int row, int col, char[][] board, boolean[][] path, TrieNode cur, String curStr, List<String> result) {
        if (row < 0 || row >= board.length || col < 0 || col >= board[0].length || path[row][col])
            return;
        char curChar = board[row][col];
        if (!cur.node.containsKey(curChar))
            return;
        cur = cur.node.get(curChar);
        curStr += curChar;
        path[row][col] = true;
        if (cur.isEnd) {
            cur.isEnd = false;
            result.add(curStr);
        }

        dfsFindWord(row, col + 1, board, path, cur, curStr, result);
        dfsFindWord(row, col - 1, board, path, cur, curStr, result);
        dfsFindWord(row + 1, col, board, path, cur, curStr, result);
        dfsFindWord(row - 1, col, board, path, cur, curStr, result);

        path[row][col] = false;
    }

    public void buildTrieNode(String[] words) {
        for (String word : words) {
            TrieNode cur = root;
            char[] data = word.toCharArray();
            for (char val : data) {
                if (!cur.node.containsKey(val))
                    cur.node.put(val, new TrieNode());
                cur = cur.node.get(val);
            }
            cur.isEnd = true;
        }
    }