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.

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

思路: 如果用BFS来做的话,

复杂度: time 是MN26^L, space: 26^L, 用Trie来做, 先建立Trie树,把words添加到trie中,然后用BFS 去遍历board,找满足的点。 找的时候需要剪枝。

public class Solution {
    public int[] xDir = new int[]{-1, 0, 1, 0};
    public int[] yDir = new int[]{0, 1, 0, -1};
    public class TrieNode {
        HashMap<Character, TrieNode> children;
        boolean hasWord;
        public TrieNode() {
            this.children = new HashMap<Character, TrieNode>();
            this.hasWord = false;
        }
    }

    public class Trie {
        TrieNode root;
        public Trie() {
            root = new TrieNode();
        }
        public void insert(String word) {
            if (word == null || word.length() == 0) return;
            TrieNode current = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (!current.children.containsKey(c)) {
                    current.children.put(c, new TrieNode());
                }
                current = current.children.get(c);
            }
            current.hasWord = true;
        }

        public boolean search(String word) {
            if (word == null || word.length() == 0) return false;
            TrieNode current = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (!current.children.containsKey(c)) {
                    return false;
                }
                current = current.children.get(c);
            }
            return current.hasWord;
        }
    }


    public List<String> findWords(char[][] board, String[] words) {
        List<String> res = new ArrayList<>();
        if (board == null || board.length == 0 || board[0] == null || 
            board[0].length == 0 || words.length == 0 || words == null)
            return res;
        // build Trie tree
        Trie trie = new Trie();
        for (String word: words) {
            trie.insert(word);
        }
        StringBuilder sb = new StringBuilder();
        // search words in board
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                search(board, trie.root, i, j, res, sb);
            }
        }  
        return res;
    }

    public void search(char[][] board, TrieNode root, int x, int y, List<String> res, StringBuilder sb) {
        if (!isValid(board, x, y)) return;
        char c = board[x][y];
        TrieNode current = root.children.get(c);
        // check edge case
        if (c == '#' || current == null) return;
        sb.append(c);
        if (root.hasWord) { // check has a word
            res.add(sb.toString());
            root.hasWord = false;
        }

        board[x][y] = '#'; // pruning
        for (int k = 0; k < 4; k++) { // explore 4 directions
            int newX = x + xDir[k];
            int newY = y + yDir[k];
            search(board, current, newX, newY, res, sb);
        }
        sb.setLength(sb.length() - 1);
        board[x][y] = c;
    } 

    public boolean isValid(char[][] board, int x, int y) {
        if (x < 0 || x >= board.length || y < 0 || y>= board[0].length) return false;
        return true;
    }
}
Advertisements