Leetcode--Java--212. 单词搜索 II

本文主要是介绍Leetcode--Java--212. 单词搜索 II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

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

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

样例描述

思路

Tire树 + 哈希表

1. 将所有的单词放到Trie树上，只要是在树的一个分支上走，就一定会有单词，如果走不通或者没有分支，就说明没有这个单词。
   
2. 哈希表维护所有的单词。
3. 本质上用Tire树来做剪枝，将所有可能的单词（路径）放到Tire树上。

代码

class Solution {//构造结点class TreeNode{String s; //记录当前结尾字符为sTreeNode tns[] = new TreeNode[26];}      TreeNode root = new TreeNode(); //根结点//实现Trie插入单词public void insert(String word) {TreeNode p = root;for (char c: word.toCharArray()) {int u = c - 'a';if (p.tns[u] == null

这篇关于Leetcode--Java--212. 单词搜索 II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---