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:

`{"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

Challenge

Using trie to implement your algorithm.

Tags

LintCode Copyright Airbnb Trie Backtracking

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.

Analysis

这一题的基本思路与Word Search是相似的，都是需要寻找在一个alphabet soup中是否存在word，可以用DFS recursion的办法来寻找。不过对于Word Search II，因为事先存在一个words dictionary，所以可以利用Trie的数据结构来存储，提高查询效率。

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)) {
                ans.add(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())) {
            res.add(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())) {
            res.add(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;
    }

Reference

Jiuzhang Word Search II

PreviousAdd and Search Word NextLongest Word in Dictionary

Last updated 3 years ago