leetcode.201 Word Search II

*Check whether a word in a board

• Solution1: backtracking || dfs
• Solution2: Trie

  class solution1{
  	Set<String> res = new HashSet<>();
  	public List<String> findWords(char[][] board, String[] words){
  		if(!res.contains(word) && exist(board, word)){
  			res.add(word);
  		}
  		return new ArrayList<>(res);
  	}
  
  	private boolean exist(char[][] board, String word){
  		int m = board.length;
  		int n = board[0].length;
  		boolean[][] visisted = new boolean[m][n];
  		for(int i = 0; i < m; i++){
  			for(int j = 0; j < n; j++){
  				if(dfs(board, i, j, word, 0, visited)) return true;
  		}
  		return false;
  		}
  	}
  	private boolean dfs(char[][] board, int i, int j, String word, int index, boolean[][] visited){
  		if(index == word.length()){ return true;
  		boolean ret = false;
  		if(dfs(board, i+1, j, word, index+1, visited) || dfs(board, i-1, j, index +1, visited) ||
  		dfs(board, i, j+1, word, index+1, visited) || dfs(board, i, j-1, index + 1, visited) || 
  		dfs(board, i, j-1, word, index+1, visited)) ret = true;
  		visited[i][j] = false;
  		}
  		return ret;
  	}
  	private boolean inboard(char[][] board, int i, int j){
  		return i >= 0 && i < board.length && j >= 0 && j <board[0].length;
  	}
  }

Solution2: trie + dfs + backtracking

• Trie implementation

  	class TrieNode {
  		public TrieNode[] children = new TrieNode[26];
  		public String item = "";
  		public TrieNode(){
  		}
  	}
  
  	class Trie(){
  		private TrieNode root;
  		public Trie(){
  			root = new TrieNode();
  		}
  
  		//insert method -> like data preprocess
  		public void insert(String word){
  			TrieNode node = root;
  			for(char c: word.toCharArray()){
  				if(node.children[c-'a']==null){
  					node.children[c-'a'] = new TrieNode();
  				}
  				node = node.children[c-'a'];
  			}
  			node.item = word; // the last node with the word
  		}
  
  		public boolean search(String word){
  			TrieNode node = root;
  			for(char c: word.toCharArray()){
  				if(node.children[c-'a']==null) return false;
  				node = node.children[c-'a'];
  			}
  			//at the end, check the item == word
  			return node.item.equals(word);
  		}
  		//check whether there is any word in the trie which start with the given prefix
  		public boolean startsWith(String prefix){
  			TrieNode node =root;
  			for(char c: prefix.toCharArray()){
  				if(node.children[c-'a']==null) return false;
  				node = node.children[c-'a'];
  			}
  			return true;
  		}
  }

solution II

using trie, the time complexity got decreased while the space will be cratically increased!
so, when the words is big, the memory space limited will be hit!
Trie can be used in small dataset with a high performance!

class solutionII{
	Set<String> res = new HashSet<String>();
	public List<String> findwords(char[][] board, String[] words){
		Trie trie = new Trie();
		for(String word: words){
			trie.insert(word);
		}
		int m = board.length;
		int n = board[0].length;
		boolean[][] visited = new boolean[m][n];
		for(int i = 0; i < m; i++){
			for(int j = 0; j < n; j++){
				dfs(board, visited, "", i, j, trie);
			}
		}
		return new ArrayList<String>(res);
	}
	private void dfs(char[][] board, boolean[][] visited, String str, int x, int y, Trie trie){
		if (x < 0 || x >= board.length || y < 0 || y >= board[0].length) return;
        if (visited[x][y]) return;

        str += board[x][y];
        if(!trie.startsWith(str)) return;
        if(trie.search(str)){
        	res.add(str);
        }
        //still backtrack
        visited[x][y] = true;
        dfs(board, visited, str, x - 1, y, trie);
        dfs(board, visited, str, x + 1, y, trie);
        dfs(board, visited, str, x, y - 1, trie);
        dfs(board, visited, str, x, y + 1, trie);
        visited[x][y] = false;
	}
}