LeetCode·212·单词搜索 II 算尽天下系列第4期

1258 0 2020年2月16日
0 0 投票数
评分

本文写于 2020年02月16日，距今已超过 1 年，距 2020年03月26日 的最后一次修改也已超过 3 个月，部分内容可能已经过时，您可以按需阅读。如果图片无法显示或者下载链接失效，请给我反馈，谢谢！


LeetCode 212 单词搜索 II

题目描述

给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

说明:

你可以假设所有输入都由小写字母 a-z 组成。

提示:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-search-ii

样例

样例输入

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

样例输出

["eat","oath"]

算法与数据结构

前缀树
深度优先搜索

题解

这道题的质量非常高，可以优化的地方非常多，因此是锻炼思路的好题目。

首先可以明确的是，暴力法一定能做。利用深度优先搜索可以完成矩阵的搜索，然后对于搜索出的单词，去找字典中有没有。

与字典比对的过程，可以是线性的；如果先排序、再二分，也可以优化成对数的；甚至可以把字典变成哈希集合，变成常数时间完成匹配。

但是这样并不能进行前缀的比对，也就是说，要么是依次完整的深度优先搜索，要么就是搜索长度为字典中最长的单词的长度。因此，这样的做法不是很高效，需要优化回溯过程，这一点在题目的提示中就说了，所以这里不详细展开，关键地方在于是不是可以提前结束回溯过程。

一种非常常见的做法是利用前缀树。前缀树被广泛地运用在字典查找当中，因此也被称为字典树。如果你不知道前缀树，可以去看一下力扣 208 题。

这里先简单给出线段树的实现代码。

class Trie {

    private TireNode root;

    /** Initialize your data structure here. */
    public Trie() {
        root = new TireNode();
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        TireNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (!node.contains(c)) {
                node.put(c);
            }
            node = node.get(c);
        }
        node.setEnd();
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TireNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (node.contains(c)) {
                node = node.get(c);
            } else {
                return false;
            }
        }
        return node.isEnd();
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TireNode node = root;
        for (int i = 0; i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            if (node.contains(c)) {
                node = node.get(c);
            } else {
                return false;
            }
        }
        return true;
    }
}

class TireNode {
    private HashMap<Character, TireNode> links;
    private boolean end;

    public TireNode() {
        links = new HashMap<>();
        end = false;
    }

    public boolean isEnd() {
        return end;
    }

    public void setEnd() {
        end = true;
    }

    public TireNode get(char c) {
        return links.get(c);
    }

    public void put(char c) {
        links.put(c, new TireNode());
    }

    public boolean contains(char c) {
        return links.containsKey(c);
    }
}

这里需要说明一下，对于本题来说，所有单词只会出现在 a - z 中，所以开一个长度为 26 的数组，可以更加节省空间，而且在插入和查询时可以有更高效的速度，但是这里给出的前缀树是更一般的形式，可以至此更多形式的字符，因此使用了 <K, V> 对的形式的 HashMap。同时，这段代码的实现还有可以优化的地方。

构建好了前缀树以后，每次从矩阵的某个字符出发进行 dfs，每搜索一层，就在前缀树进行一次比对，看是不是存在以当前为前缀的单词。

在任意一层发现不存在以当前为前缀的单词时，则直接停止深搜。

如果当前前缀存在，则继续往下深搜。

特别的，如果当前前缀可以作为一个完整单词存在，那就输出该结果。

需要注意的是，输出单词后并不能结束搜索，因为可能存在 ad 是一个单词、advanced 也是一个单词，因此，即便 ad 的 end 是 true，输出 ad 之后也需要继续往下搜索。

深搜的代码比较简单，这里不详细说了。

说明几点，我处理是不是访问过，是直接修改了 board[][] 为空格字符 ' '，这个做法可能不太合适，因为不管修改为什么字符，这个字符也都可能是合法单词的一部分，我们不能假设单词中一定会有一个字符永远不会出现。因此，更加合理的做法是开一个 boolean visited[][] 数组。

另外，当前字符串 prefix 与当前字符 c 拼接的时候，我直接做了 String 和 char 的加法，这个操作会有多少额外的花销，也是可以说道说道的。

但是反正 StringBuilder 这种会改变自己的值的类作为基本类型做递归传递的时候会有很多麻烦的事，我就懒得做了，而且 String + char 在 Java 具体操作的时候，会调用性能更高的 Builder 来做，那就也无所谓了。

为了避免同一个单词被加入多次，这里的结果保存在了 Set 中，并最后通过 Collection 的构造函数直接变成了一个 List。

void dfs(char[][] board, int i, int j, String prefix) {
    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
        return; // 越界
    }
    char c = board[i][j]; // 记录当前位置
    if (c != ' ') {
        // 如果没访问过当前位置，设置为已访问（置空格），然后 append 到 prefix（prefix += c）
        board[i][j] = ' ';
        prefix += c;
        // 如果存在前缀，继续，否则没必要往下了，直接 return
        if (trie.startsWith(prefix)) {
            // 如果该前缀恰好也是一个单词的结束，则加入 result
            if (trie.search(prefix)) {
                result.add(prefix);
            }
            // 深搜
            dfs(board, i, j + 1, prefix);
            dfs(board, i + 1, j, prefix);
            dfs(board, i - 1, j, prefix);
            dfs(board, i, j - 1, prefix);
        }
        // 还原棋盘当前位置
        board[i][j] = c;
    }
}

至此，代码就完成了，只需补上输入输出、然后开始的时候录遍历字典插入前缀树就可以了。

for (String word : words) {
    trie.insert(word);
}
int rows = board.length;
int cols = board[0].length;
//从每个位置开始遍历，查询前缀 prefix 是否符合要求
String prefix = "";
for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
        dfs(board, i, j, prefix);
    }
}
return new ArrayList<>(result); // 最后把 Set 转化为 List 返回

但是这道题到这里并没有结束。

考虑这样一种情况，有单词 angry 和 angle，当遍历到路径 a - n 的时候，我已经知道了这是前缀树的一条路径，an 是一个合法的前缀，于是继续往后，扫描到 g，根据我们之前的做法，下面要做的事情是判断 ang 是不是一个合法的前缀，在判断 ang 的时候，我们又走了一遍从前缀树 root 到 a 到 n 的路径。

那么，我能不能把这条路径省了呢，我能不能直接从上一个 TrieNode 开始遍历，而不从 Trie 的根结点开始呢？当然可以。只需要修改前缀树的实现，将单词保存在每一个节点即可。

当然，可能还需要修改前缀树暴露的接口，使得可以直接访问任意一层结点，而不是只能访问根结点。

我们在 Node 中增加一个字段 String word，当 end == true 时，记录该单词，否则，若 end == false，则保证 word == null。

于是，在递归过程中，我们只需判断当前节点的 word 是不是为 null，如果不是，就输出结果，如果是，则继续递归。

这样就避免了反复搜索前缀树路径的过程。

这个修改比较简单，我也就懒得写了，如果您有兴趣，不妨根据我下面的完整代码，稍作修改，进一步提升代码的效率。

完整代码

class Solution {

    private Trie trie = new Trie(); // 前缀树
    private HashSet<String> result = new HashSet<>(); // 用 Set 避免重复添加（去重）

    public List<String> findWords(char[][] board, String[] words) {
        for (String word : words) {
            trie.insert(word);
        }
        int rows = board.length;
        int cols = board[0].length;
        //从每个位置开始遍历，查询前缀 prefix 是否符合要求
        String prefix = "";
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                dfs(board, i, j, prefix);
            }
        }
        return new ArrayList<>(result); // 最后把 Set 转化为 List 返回
    }

    private void dfs(char[][] board, int i, int j, String prefix) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
            return; // 越界
        }
        char c = board[i][j]; // 记录当前位置
        if (c != ' ') {
            // 如果没访问过当前位置，设置为已访问（置空格），然后 append 到 prefix（prefix += c）
            board[i][j] = ' ';
            prefix += c;
            // 如果存在前缀，继续，否则没必要往下了，直接 return
            if (trie.startsWith(prefix)) {
                // 如果该前缀恰好也是一个单词的结束，则加入 result
                if (trie.search(prefix)) {
                    result.add(prefix);
                }
                // 深搜
                dfs(board, i, j + 1, prefix);
                dfs(board, i + 1, j, prefix);
                dfs(board, i - 1, j, prefix);
                dfs(board, i, j - 1, prefix);
            }
            // 还原棋盘当前位置
            board[i][j] = c;
        }
    }
}

class Trie {

    private TireNode root;

    /**
     * Initialize your data structure here.
     */
    public Trie() {
        root = new TireNode();
    }

    /**
     * Inserts a word into the trie.
     */
    public void insert(String word) {
        TireNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (!node.contains(c)) {
                node.put(c);
            }
            node = node.get(c);
        }
        node.setEnd();
    }

    /**
     * Returns if the word is in the trie.
     */
    public boolean search(String word) {
        TireNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (node.contains(c)) {
                node = node.get(c);
            } else {
                return false;
            }
        }
        return node.isEnd();
    }

    /**
     * Returns if there is any word in the trie that starts with the given prefix.
     */
    public boolean startsWith(String prefix) {
        TireNode node = root;
        for (int i = 0; i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            if (node.contains(c)) {
                node = node.get(c);
            } else {
                return false;
            }
        }
        return true;
    }
}

class TireNode {
    private HashMap<Character, TireNode> links;
    private boolean end;

    public TireNode() {
        links = new HashMap<>();
        end = false;
    }

    public boolean isEnd() {
        return end;
    }

    public void setEnd() {
        end = true;
    }

    public TireNode get(char c) {
        return links.get(c);
    }

    public void put(char c) {
        links.put(c, new TireNode());
    }

    public boolean contains(char c) {
        return links.containsKey(c);
    }

}
0 0 投票数
评分
发表留言
订阅评论
提醒
guest

在点击发表评论按钮时，网络请求的数据包含浏览器版本、操作系统版本和 IP 地址；您的网络服务提供商、雇主或学校、政府机构可能会看到您的访问活动；根据浏览器默认行为、操作系统设置和安全防护软件的设置不同，您的浏览器可能会也可能不会在本地 Cookies 缓存您输入的用户名、邮箱以便下次评论使用。

请对自己的言行负责。

您想以什么身份发表评论
邮箱将在您的评论被回复时给您通知
（可选）如果您也有个人网站，不妨分享一下
我对这篇文章的评分
这篇文章给您带来多大帮助
0 评论
内联反馈
查看所有评论