Word Search II

1package pkg5leetcode.blind75;2 3/*4 * Word Search II | LC 2125 * APPROACH: Trie of words + DFS on board pruning by trie paths.6 * COMPLEXITY: Time O(mn * 4^L), Space O(total word chars)7 */8import java.util.*;9 10public class blind75_LC212WordSearchII {11    static class TrieNode {12        TrieNode[] child = new TrieNode[26];13        String word;14    }15 16    static TrieNode root = new TrieNode();17 18    static void insert(String word) {19        TrieNode node = root;20        for (char c : word.toCharArray()) {21            int i = c - 'a';22            if (node.child[i] == null) node.child[i] = new TrieNode();23            node = node.child[i];24        }25        node.word = word;26    }27 28    static List<String> findWords(char[][] board, String[] words) {29        root = new TrieNode();30        for (String w : words) insert(w);31        List<String> res = new ArrayList<>();32        for (int i = 0; i < board.length; i++)33            for (int j = 0; j < board[0].length; j++)34                dfs(board, i, j, root, res);35        return res;36    }37 38    static void dfs(char[][] b, int r, int c, TrieNode node, List<String> res) {39        if (node.word != null) { res.add(node.word); node.word = null; }40        if (r < 0 || c < 0 || r >= b.length || c >= b[0].length) return;41        char ch = b[r][c];42        if (ch == '#' || node.child[ch - 'a'] == null) return;43        TrieNode next = node.child[ch - 'a'];44        b[r][c] = '#';45        dfs(b, r + 1, c, next, res);46        dfs(b, r - 1, c, next, res);47        dfs(b, r, c + 1, next, res);48        dfs(b, r, c - 1, next, res);49        b[r][c] = ch;50    }51 52    public static void main(String[] args) {53        char[][] board = {{'o','a','a','n'},{'e','t','a','e'},{'i','h','k','r'},{'i','f','l','v'}};54        List<String> r = findWords(board, new String[]{"oath","pea","eat","rain"});55        check(r.contains("eat") && r.contains("oath"), "case1");56        List<String> r2 = findWords(new char[][]{{'a'}}, new String[]{"a"});57        check(r2.equals(Collections.singletonList("a")), "case2");58        System.out.println("all tests passed");59    }60 61    static void check(boolean cond, String name) {62        if (!cond) throw new AssertionError("FAILED: " + name);63        System.out.println("  PASS " + name);64    }65}