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

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

Solution:

This is similar to Word Search. However, instead of compare only one word, we need to compare a list of words. Since we only compare one character at a time, trie would be a great choice to verify that current character is useful or not.

Code:

public class Solution {
    /**
     * @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> res = new ArrayList<>();
        if (words == null || words.size() == 0) {
            return res;
        }
        if (board == null || board.length == 0) {
            return res;
        }
        Trie trie = createTrie(words);
        HashSet<Integer> visited = new HashSet<>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                go(i, j, board, trie, new StringBuilder(), res, visited);
            }
        }
        return res;
    }

    private Trie createTrie(List<String> words) {
        Trie trie = new Trie();
        for (String word : words) {
            trie.insert(word);
        }
        return trie;
    }

    private void go(int i, int j, char[][] board, Trie trie, StringBuilder sb,
                    List<String> res, Set<Integer> visited) {
        if (i < 0 || i >= board.length) {
            return;
        }
        if (j < 0 || j >= board[0].length) {
            return;
        }
        int index = i * board[0].length + j;
        if (visited.contains(index)) {
            return;
        }
        sb.append(board[i][j]);
        visited.add(index);
        String temp = sb.toString();
        if (trie.search(temp) && !res.contains(temp)) {
            res.add(temp);
        }
        if (trie.prefix(temp)) {
            go(i - 1, j, board, trie, sb, res, visited);
            go(i + 1, j, board, trie, sb, res, visited);
            go(i, j + 1, board, trie, sb, res, visited);
            go(i, j - 1, board, trie, sb, res, visited);
        }
        visited.remove(index);
        sb.setLength(sb.length() - 1);
    }
}

class Trie {
    class TrieNode {
        TrieNode[] next;
        boolean isWord;
        public TrieNode() {
            next = new TrieNode[26];
            isWord = false;
        }
    }
    TrieNode root;
    public Trie() {
        root = new TrieNode();
    }
    public void insert(String word) {
        if (word == null || word.length() < 0) {
            return;
        }
        TrieNode p = root;
        for (int i = 0; i < word.length(); i++) {
            int c = word.charAt(i) - 'a';
            if (p.next[c] == null) {
                p.next[c] = new TrieNode();
            }
            p = p.next[c];
        }
        p.isWord = true;
    }
    public boolean search(String word) {
        if (word == null || word.length() < 0) {
            return false;
        }
        TrieNode p = root;
        for (int i = 0; i < word.length(); i++) {
            int c = word.charAt(i) - 'a';
            if (p.next[c] == null) {
                return false;
            }
            p = p.next[c];
        }
        return p.isWord;
    }
    public boolean prefix(String word) {
        if (word == null || word.length() < 0) {
            return false;
        }
        TrieNode p = root;
        for (int i = 0; i < word.length(); i++) {
            int c = word.charAt(i) - 'a';
            if (p.next[c] == null) {
                return false;
            }
            p = p.next[c];
        }
        return p != null;
    }
}