Leetcode 212 Word Search II

Given a 2D board and a list of words from the dictionary, find all words in the board.

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

For example,
Given words = ["oath","pea","eat","rain"] and board =

[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

Return ["eat","oath"].

Note:
You may assume that all inputs are consist of lowercase letters a-z.

Solution 1: the combination of graph and trie. First use dictionary to build the trie. Then DFS the char array to come up the result list.

 public class Solution {  
   class TrieNode {  
     private boolean val=false;  
     private TrieNode[] next=new TrieNode[26];  
   }  
   private TrieNode root=new TrieNode();  
   private void add(String word) {  
     TrieNode x=root;  
     int i=0;  
     while (i<word.length()) {  
       int index=word.charAt(i++)-'a';  
       if (x.next[index]==null) x.next[index]=new TrieNode();  
       x=x.next[index];  
     }  
     x.val=true;  
   }  
   private TrieNode search(String word) {  
     TrieNode x=root;  
     int i=0;  
     while (i<word.length()) {  
       int index=word.charAt(i++)-'a';  
       if (x.next[index]==null) return null;  
       x=x.next[index];  
     }  
     return x;  
   }  
   private boolean findOne(String word) {  
     TrieNode x=search(word);  
     if (x==null) return false;  
     return x.val;  
   }  
   private boolean findPrefix(String word) {  
     TrieNode x=search(word);  
     if (x==null) return false;  
     return true;  
   }  
   public List<String> findWords(char[][] board, String[] words) {  
     Set<String> res=new HashSet<>();  
     for (String s:words) add(s);  
     int m=board.length;  
     if (m==0) return new ArrayList<String>(res);  
     int n=board[0].length;  
     String s="";  
     for (int i=0; i<m; i++) {  
       for (int j=0; j<n; j++) {  
         dfs(board,i,j,m,n,s,res);  
       }  
     }  
     return new ArrayList<String>(res);  
   }  
   private void dfs(char[][] board, int i, int j, int m, int n, String s, Set<String> res) {  
     if (i<0 || i>=m) return;  
     if (j<0 || j>=n) return;  
     if (board[i][j]=='.') return;  
     char c=board[i][j];  
     String word=s+c;  
     if (!findPrefix(word)) return;  
     if (findOne(word)) res.add(word);  
     board[i][j]='.';  
     dfs(board,i+1,j,m,n,word,res);  
     dfs(board,i-1,j,m,n,word,res);  
     dfs(board,i,j+1,m,n,word,res);  
     dfs(board,i,j-1,m,n,word,res);  
     board[i][j]=c;  
   }  
 }