Leetcode 212: 单词搜索II

题目描述

给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

示例:

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

输出: ["eat","oath"]
说明:
你可以假设所有输入都由小写字母 a-z 组成。

提示:

你需要优化回溯算法以通过更大数据量的测试。你能否早点停止回溯？
如果当前单词不存在于所有单词的前缀中，则可以立即停止回溯。什么样的数据结构可以有效地执行这样的操作？散列表是否可行？为什么？ 前缀树如何？如果你想学习如何实现一个基本的前缀树，请先查看这个问题： 实现Trie（前缀树）。

思路

思路1: 回溯+DFS

直接使用回溯+DFS判断每个单词是否存在，需要注意一个单词不能使用两次以上一个字符。

思路2: 前缀树+回溯减枝

对所有的单词建立节点，然后回溯board中每个可能的单词，裁剪掉不能满足前缀树的路径

代码

代码1: 回溯+DFS

public class Solution {
    public List findWords(char[][] board, String[] words) {
        List result = new LinkedList<>();
        if (words.length == 0 || board.length == 0 || board[0].length == 0){
            return result;
        }
        for(String word: words){
            if(hasWord(word, board)) {
                result.add(word);
            }
        }
        return result;
    }

    private boolean hasWord(String s, char[][] board){
        boolean canFind = false;
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if (s.charAt(0) == board[i][j] && wordDFS(s, board, 0, i, j)) {
                    canFind = true;
                    break;
                }
            }
            if (canFind){
                break;
            }
        }
        return canFind;
    }

    private boolean wordDFS(String s, char[][] board, int startIndex, int i, int j){
        if (startIndex == s.length() - 1){
            return true;
        }
        boolean canFind = false;
        char temp = s.charAt(startIndex);
        char getCh = s.charAt(startIndex + 1);
        board[i][j] = '$';
        if(canGetCh(getCh, board, i + 1, j)){
            canFind = canFind || wordDFS(s, board, startIndex+1, i+1, j);
            if (canFind){
                board[i][j] = temp;
            }
        }
        if (!canFind && canGetCh(getCh, board, i -1, j)){
            canFind = canFind || wordDFS(s, board, startIndex+1, i-1, j);
            if (canFind){
                board[i][j] = temp;
            }
        }
        if (!canFind && canGetCh(getCh, board, i, j+1)){
            canFind = canFind || wordDFS(s, board, startIndex+1, i, j+1);
            if (canFind){
                board[i][j] = temp;
            }
        }
        if (!canFind && canGetCh(getCh, board, i, j-1)){
            canFind = canFind || wordDFS(s, board, startIndex+1, i, j-1);
            if (canFind){
                board[i][j] = temp;
            }
        }
        board[i][j] = temp;
        return canFind;
    }

    private boolean canGetCh(char getCh, char[][] board, int i, int j){
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length){
            return false;
        }
        return board[i][j] == getCh;
    }
}