Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can 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.

Example

Given board =

[
  "ABCE",
  "SFCS",
  "ADEE"
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

public boolean exist(char[][] board, String word) {
    if(board == null || board.length == 0 || board[0].length == 0) {
        return false;
    }
    int m = board.length, n = board[0].length;
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            if(board[i][j] == word.charAt(0)) {
                if(dfs(board, i, j, word, 0)) {
                    return true;
                }
            }
        }
    }
    return false;
}
public boolean dfs(char[][] board, int i, int j, String word, int index) {
    if(index == word.length()) {
        return true;
    }
    if(i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] == '!') {
        return false;
    }
    if(board[i][j] != word.charAt(index)) {
        return false;
    }
    char tmp = board[i][j];
    board[i][j] = '!';
    boolean bool = dfs(board, i + 1, j, word, index + 1) || dfs(board, i - 1, j, word, index + 1) ||
                   dfs(board, i, j + 1, word, index + 1) || dfs(board, i, j - 1, word, index + 1);
    board[i][j] = tmp;
    return bool;
}

Word Search II

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:

{"dog", "dad", "dgdg", "can", "again"}

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

dog:

doaf
agai
dcan

dad:

doaf
agai
dcan

can:

doaf
agai
dcan

again:

doaf
agai
dcan

Solution: Trie to find prefix

class TrieNode {
    TrieNode[] children;
    boolean isLeaf;
    public TrieNode() {
        children = new TrieNode[26];
        isLeaf = false;
    }
}
class Trie {
    TrieNode root;
    public Trie() {
        root = new TrieNode();
    }
    public void addWord(String word) {
        TrieNode p = root;
        for(int i = 0; i < word.length(); i++) {
            int tmp = word.charAt(i) - 'a';
            if(p.children[tmp] == null) {
                p.children[tmp] = new TrieNode();
            }
            p = p.children[tmp];
        }
        p.isLeaf = true;
    }
    public boolean search(String word) {
        TrieNode p = root;
        for(int i = 0; i < word.length(); i++) {
            int tmp = word.charAt(i) - 'a';
            if(p.children[tmp] == null) {
                return false;
            }
            p = p.children[tmp];
        }
        return p.isLeaf;
    }
    public boolean searchPrefix(String prefix) {
        TrieNode p = root;
        for(int i = 0; i < prefix.length(); i++) {
            int tmp = prefix.charAt(i) - 'a';
            if(p.children[tmp] == null) {
                return false;
            }
            p = p.children[tmp];
        }
        return true;
    }
}
public ArrayList<String> wordSearchII(char[][] board, ArrayList<String> words) {
    ArrayList<String> res = new ArrayList<String>();
    if(board == null || board.length == 0 || board[0].length == 0) {
        return res;
    }
    Trie trie = new Trie();
    for(String s : words) {
        trie.addWord(s);
    }
    for(int i = 0; i < board.length; i++) {
        for(int j = 0; j < board[0].length; j++) {
            dfs(board, i, j, new StringBuilder(), res, trie);
        }
    }
    return res;
}
public void dfs(char[][] board, int i, int j, StringBuilder sb, ArrayList<String> res, Trie trie) {
    if(i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] == '!') {
        return ;
    }
    sb.append(board[i][j]);
    if(!trie.searchPrefix(sb.toString())) {
        return ;
    }
    if(trie.search(sb.toString())) {
        if(!res.contains(sb.toString())) {
            res.add(sb.toString());
        }
    }
    char tmp = board[i][j];
    board[i][j] = '!';
    dfs(board, i + 1, j, words, res, trie);
    dfs(board, i - 1, j, words, res, trie);
    dfs(board, i, j + 1, words, res, trie);
    dfs(board, i, j - 1, words, res, trie);
    board[i][j] = tmp;
    sb.deleteCharAt(sb.length() - 1);
}