@@ -0,0 +1,1823 @@
+// Solution beats 80.91%25 of submissions.%0A//%0A// Runs in O(N*M + K*W), where N and M are dimensions of the board, and K is length of dictionary%0A// and W is the length of the word.%0A//%0A// Space complexity is O(W), where W is the length of the word, there is also a constant for%0A// children array storage, but asymptotically will be linear to the word.%0A// This also includes recursion for depth W.%0A//%0Aclass Solution %7B%0A  static class TrieNode %7B%0A    TrieNode%5B%5D children = new TrieNode%5B'z' - 'a' + 1%5D;%0A    String word = null;%0A  %7D%0A%0A  public List%3CString%3E findWords(char%5B%5D%5B%5D board, String%5B%5D words) %7B%0A    List%3CString%3E res = new ArrayList%3CString%3E();%0A    TrieNode root = new TrieNode();%0A    // build trie%0A    for (String word : words) %7B%0A      add(word, root);%0A    %7D%0A    // search words%0A    for (int i = 0; i %3C board.length; i++) %7B%0A      for (int j = 0; j %3C board%5B0%5D.length; j++) %7B%0A        search(board, i, j, root, res);%0A      %7D%0A    %7D%0A    return res;%0A  %7D%0A%0A  private void add(String word, TrieNode root) %7B%0A    for (int i = 0; i %3C word.length(); i++) %7B%0A      int idx = word.charAt(i) - 'a';%0A      if (root.children%5Bidx%5D == null) %7B%0A        root.children%5Bidx%5D = new TrieNode();%0A      %7D%0A      root = root.children%5Bidx%5D;%0A    %7D%0A    root.word = word;%0A  %7D%0A%0A  private void search(char%5B%5D%5B%5D board, int i, int j, TrieNode node, List%3CString%3E res) %7B%0A    if (i %3C 0 %7C%7C i %3E= board.length %7C%7C j %3C 0 %7C%7C j %3E= board%5B0%5D.length %7C%7C node == null %7C%7C board%5Bi%5D%5Bj%5D == '?') return;%0A    char t = board%5Bi%5D%5Bj%5D;%0A    TrieNode next = node.children%5Bt - 'a'%5D;%0A    if (next == null) return;%0A    if (next.word != null) %7B%0A      res.add(next.word);%0A      next.word = null;%0A    %7D%0A    board%5Bi%5D%5Bj%5D = '?';%0A    search(board, i+1, j, next, res);%0A    search(board, i-1, j, next, res);%0A    search(board, i, j+1, next, res);%0A    search(board, i, j-1, next, res);%0A    board%5Bi%5D%5Bj%5D = t;%0A  %7D%0A%7D%0A

add solution