Word Search II

LeetCode Q 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.

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”]

Note:

• All inputs are consist of lowercase letters a-z.
• The values of words are distinct.

Solution : Trie + DFS / Backtracking

Compared with Word Search, we use DFS with a trie but a word.

Code:

class TrieNode() {
	TrieNode[] children;
	boolean isEnd;
	public TrieNode() { this.children = new TrieNode[26]; }
}

private TrieNode root;

private void insert(String word) {
	TrieNode node = root;
	for (char ch: word.toCharArray()) {
		if (node.children[ch - 'a']) 
			node.children[ch - 'a'] = new TrieNode();
		node = node.children[ch - 'a'];
	}
	node.isEnd = true;
}

private boolean startWith(String word) {
	TrieNode node = root;
	for (char ch: word.toCharArray()) {
		if (node.children[ch - 'a'] == null) 
			return false;
		node = node.children[ch - 'a'];
	}
	return true;
}

private boolean search(String word) {
	TrieNode node = root;
	for (char ch: word.toCharArray()) {
		if (node.children[ch - 'a'] == null) 
			return false;
		node = node.children[ch - 'a'];
	}
	return node.isEnd;
}


private Set<String> res;  // avoid duplicates
public List<String> findWords(char[][] board, String[] words) {
	res = new HashSet<>();
	trie = new TrieNode();

	// build the trie
	for (String word: words) trie.insert(word);

	boolean[][] visited = new [board.length][board[0].length];
	for (int i = 0; i < board.length; i++) {
		for (int j = 0; j < board[i].length; j++) {
			dfs(board, "", i, j, visited);
		}
	}

	return new ArrayList(res);
}

private void dfs(char[][] board, String curr, int row, int col, boolean[][] visited) {

	if (row < 0 || row == board.length || col < 0 || col > board[0].length || visited[row][col]) 
		return false;

	curr += board[row][col];
	if (!startWith(curr)) return;
	if (search(curr)) { res.add(curr); } //return, shouldn't return keep searching
 
	visited[row][col] = true;
	dfs(board, row + 1, col, visited);
	dfs(board, row - 1, col, visited);
	dfs(board, row, col + 1, visited);
	dfs(board, row, col - 1, visited);
	visited[row][col] = false;

	return;
}

Tips:
In the dfs function, when the string curr is added to the res, if the code then return at once, the algorithm is wrong.

For example:
input:
a  b
a  a
word list is: ["aba","baa","bab","aaab","aaa","aaaa","aaba"]
The expected answer is: [“aaa”,”aaab”,”aaba”,”aba”,”baa”]

Suppose we find aaa and add it in the set and then we return, we cannot get aaab.