# Word Search II

## Question

Given a matrix of lower alphabets and a dictionary. Find all words in the dictionary that can be found in the matrix. A word can start from any position in the matrix and go left/right/up/down to the adjacent position.

Example

Given matrix:

``````doaf
agai
dcan``````

and dictionary:

return `{"dog", "dad", "can", "again"}`

dog:

``````doaf
agai
dcan``````

``````doaf
agai
dcan``````

can:

``````doaf
agai
dcan``````

again:

``````doaf
agai
dcan``````

Challenge

Using trie to implement your algorithm.

Tags

Another Version

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.

Hint:

You would need to optimize your backtracking to pass the larger test. Could you stop backtracking earlier?

If the current candidate does not exist in all words' prefix, you could stop backtracking immediately. What kind of data structure could answer such query efficiently? Does a hash table work? Why or why not? How about a Trie? If you would like to learn how to implement a basic trie, please work on this problem: Implement Trie (Prefix Tree) first.

## Solution

``````class TrieNode {
char c;
HashMap<Character, TrieNode> children;
boolean isLeaf;
String s;

public TrieNode() {
this.children = new HashMap<Character, TrieNode>();
this.s = "";
}

public TrieNode(char c) {
this.c = c;
this.s = "";
this.children = new HashMap<Character, TrieNode>();
this.isLeaf = false;
}
}

class Trie {
public TrieNode root;

public Trie() {
root = new TrieNode();
}

public void insert(String word) {
HashMap<Character, TrieNode> children = root.children;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);

TrieNode t;
if (children.containsKey(c)) {
t = children.get(c);
} else {
t = new TrieNode(c);
children.put(c, t);
}

children = t.children;

if (i == word.length() - 1) {
t.isLeaf = true;
t.s = word;
}
}
}

public boolean search(String word) {
TrieNode t = searchTrieNode(word);
if (t != null && t.isLeaf) {
return true;
} else {
return false;
}
}

public TrieNode searchTrieNode(String str) {
HashMap<Character, TrieNode> children = root.children;
TrieNode t = null;

for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (children.containsKey(c)) {
t = children.get(c);
children = t.children;
} else {
return null;
}
}

return t;
}
}

public class Solution {
int[] dirX = {0, 0, 1, -1};
int[] dirY = {-1, 1, 0, 0};

public void searchWord(char[][] board, int i, int j, TrieNode root, ArrayList<String> ans) {
if (root.isLeaf == true) {
if (!ans.contains(root.s)) {
}
}
if (i >= 0 && i < board.length &&
j >= 0 && j < board[0].length &&
board[i][j] != '#' && root != null) {

if (root.children.containsKey(board[i][j])) {
for (int k = 0; k < 4; k++) {
int x = i + dirX[k];
int y = j + dirY[k];
char temp = board[i][j];
board[i][j] = '#';
searchWord(board, x, y, root.children.get(temp), ans);
board[i][j] = temp;
}
}
}
}
/**
* @param board: A list of lists of character
* @param words: A list of string
* @return: A list of string
*/
public ArrayList<String> wordSearchII(char[][] board, ArrayList<String> words) {
ArrayList<String> ans = new ArrayList<String>();

Trie trie = new Trie();
for (String word : words) {
trie.insert(word);
}

for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
searchWord(board, i, j, trie.root, ans);
}
}

return ans;
}
}``````

Trie + DFS (28ms, 54.88% AC)

``````class Solution {
class TrieNode {
TrieNode[] next = new TrieNode[26];
String word;
TrieNode get(char ch) {
return next[ch - 'a'];
}
void put(char ch, TrieNode node) {
next[ch - 'a'] = node;
}
void setWord(String s) {
word = s;
}
String getWord() {
return word;
}
}
private TrieNode buildTrie(String[] words) {
TrieNode root = new TrieNode();
for (String word : words) {
TrieNode node = root;
char[] charArray = word.toCharArray();
for (char ch : charArray) {
if (node.get(ch) == null) {
node.put(ch, new TrieNode());
}
node = node.get(ch);
}
node.setWord(word);
}
return root;
}
public List<String> findWords(char[][] board, String[] words) {
TrieNode root = buildTrie(words);
System.out.println(root.word);
List<String> res = new ArrayList<String>();
int M = board.length;
int N = board[0].length;
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
dfsHelper(board, i, j, root, res);
}
}
return res;
}
private void dfsHelper(char[][] board, int i, int j, TrieNode node, List<String> res) {
if (i < 0 || j < 0 || i >= board.length || j >= board[0].length) return;
if (node == null || board[i][j] == '#') return;
char ch = board[i][j];
node = node.get(ch);
if (node != null && node.getWord() != null && !res.contains(node.getWord())) {
}
int[] dx = new int[] {0, 1, 0, -1};
int[] dy = new int[] {1, 0, -1, 0};

board[i][j] = '#';
for (int k = 0; k < 4; k++) {
dfsHelper(board, i + dx[k], j + dy[k], node, res);
}
board[i][j] = ch;
}
}``````
``````    private void dfsHelper(char[][] board, int i, int j, TrieNode node, List<String> res) {
char ch = board[i][j];
if (board[i][j] == '#' || node == null || node.get(ch) == null) return;
node = node.get(ch);
if (node.getWord() != null && !res.contains(node.getWord())) {
}
int[] dx = new int[] {0, 1, 0, -1};
int[] dy = new int[] {1, 0, -1, 0};

board[i][j] = '#';
for (int k = 0; k < 4; k++) {
int newI = i + dx[k];
int newJ = j + dy[k];
if (newI >= 0 && newJ >= 0 && newI < board.length && newJ < board[0].length) {
dfsHelper(board, newI, newJ, node, res);
}
}
board[i][j] = ch;
}``````

Last updated