212. Word Search II (M)

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example 1:

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

Example 2:

Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []

Constraints:

• m == board.length

• n == board[i].length

• 1 <= m, n <= 12

• board[i][j] is a lowercase English letter.

• 1 <= words.length <= 3 * 104

• 1 <= words[i].length <= 10

• words[i] consists of lowercase English letters.

• All the strings of words are unique.

Solution:

https://www.jiuzhang.com/problem/word-search-ii/ Version Trie:

使用了 Trie 的版本 考点：

• 字典树

• dfs

• tip:Tire树，一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。

题解：

• 首先建立字典树，字典树从root开始，每个节点利用hashmap动态开点，利用字母的公共前缀建树。

• 遍历字母矩阵，将字母矩阵的每个字母，从root开始dfs搜索，搜索到底部时，将字符串存入答案返回即可。

class TrieNode {			//定义字典树的节点
    String word;
    HashMap<Character, TrieNode> children;   //使用HashMap动态开节点
    public TrieNode() {
        word = null;
        children = new HashMap<Character, TrieNode>();
    }
};


class TrieTree{
    TrieNode root;
    
    public TrieTree(TrieNode TrieNode) {
        root = TrieNode;
    }
    
    public void insert(String word) {		//字典树插入单词
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {		
            if (!node.children.containsKey(word.charAt(i))) {
                node.children.put(word.charAt(i), new TrieNode());
            }
            node = node.children.get(word.charAt(i));
        }
        node.word = word;
    }
};

public class Solution {
    /**
     * @param board: A list of lists of character
     * @param words: A list of string
     * @return: A list of string
     */
    public int[] dx = {1, 0, -1, 0};   //搜索方向
    public int[] dy = {0, 1, 0, -1};
    
    public void search(char[][] board,			//在字典树上dfs查找
                       int x,
                       int y,
                       TrieNode root,
                       List<String> results) {
        if (!root.children.containsKey(board[x][y])) {
            return;
        }
        
        TrieNode child = root.children.get(board[x][y]);
        
        if (child.word != null) {      //如果访问到字典树叶子，将字符串压入result即可
            if (!results.contains(child.word)) {
                results.add(child.word);
            }
        }
        
        char tmp = board[x][y];
        board[x][y] = 0;  // mark board[x][y] as used
        
        for (int i = 0; i < 4; i++) {      //向四个方向dfs搜索
            if (!isValid(board, x + dx[i], y + dy[i])) {
                continue;
            }
            search(board, x + dx[i], y + dy[i], child, results);
        }
        
        board[x][y] = tmp;  // revert the mark
    }
    
    private boolean isValid(char[][] board, int x, int y) {     //检测搜索位置合法
        if (x < 0 || x >= board.length || y < 0 || y >= board[0].length) {
            return false;
        }
        
        return board[x][y] != 0;
    }
    
    public List<String> wordSearchII(char[][] board, List<String> words) {
        List<String> results = new ArrayList<String>();
        
        TrieTree tree = new TrieTree(new TrieNode());
        for (String word : words){
            tree.insert(word);
        }
        
        for (int i = 0; i < board.length; i++) {				//遍历字母矩阵，将每个字母作为单词首字母开始搜索
            for (int j = 0; j < board[i].length; j++) {
                search(board, i, j, tree.root, results);
            }
        }
        
        return results;
    }
}

Version 2: HashMap

使用 HashMap 的版本。 将所有的单词的 Prefix 都加入 HashMap 中。HashMap 的 value 用户判断这是一个 prefix 还是一个 word。 如果是 prefix 就是 false，如果是 word 就是 true.

class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        
        int m = board.length;
        int n = board[0].length;
        Map<String, Boolean> prefixMap = getPrefixMap(words);
        boolean[][] visited = new boolean[m][n];
        Set<String> result = new HashSet<String>();
        
        for(int i = 0; i< m;i++)
        {
            for(int j = 0; j< n; j++)
            {
                visited[i][j] = true;
                dfs(board, i, j,  String.valueOf(board[i][j]), prefixMap, visited, result);
                visited[i][j] = false;
            }
        }
         return new ArrayList<>(result);                                    
                                         
    }
    
    public Map<String, Boolean> getPrefixMap(String[] words)
    {
        Map<String, Boolean> map = new HashMap<>();
        for(String word: words)
        {
            for(int i = 0; i< word.length()-1; i++)
            {
                String current = word.substring(0,i+1);
                if(!map.containsKey(current))
                {
                    map.put(current, false);
                }
            }
            map.put(word, true);
        }
        return map;
    }
    
    public void dfs(char[][] board, 
                    int x, 
                    int y, 
                    String word, 
                    Map<String, Boolean> prefixMap,
                    boolean[][] visited, 
                    Set<String> result)
    {
        if(!prefixMap.containsKey(word))
        {
            return;
        }
        if(prefixMap.get(word))
        {
            result.add(word);
        }
        
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        for(int i=0; i< 4; i++)
        {
            int nextX = x+dx[i];
            int nextY = y+dy[i];
            if(isBound(board, nextX, nextY) && !visited[nextX][nextY])
            {
                visited[nextX][nextY] = true;
                dfs(board, nextX, nextY, word+board[nextX][nextY], prefixMap, visited, result);
                visited[nextX][nextY] = false;
            }
        }
    }
    
    public boolean isBound(char[][] board, 
                    int x, 
                    int y)
    {
        return x>=0 && x<board.length && y>=0 && y< board[0].length;
    }
}

Follow up:

Find a path:

https://app.gitbook.com/s/mJ9CI3NPRUiNTweCYXsQ/oa/karat/find-word-path-in-grid