当前位置：首页 > news >正文

LeetCode 211

news 来源：原创 2025/7/2 6:01:44

实现支持通配符的字典树（Trie）：解决单词匹配问题

一、问题描述

我们需要设计一个数据结构，支持以下功能：

添加新单词
搜索字符串是否与任何已添加的单词匹配，其中搜索字符串可能包含通配符 .（表示任意字符）。

例如：

插入单词 apple
搜索 app → false
搜索 app. → true

二、方法思路：字典树（Trie）

为什么选择字典树？

字典树是一种高效的树形结构，特别适合处理字符串的前缀匹配问题。其核心优势在于：

空间效率高：共享公共前缀，减少冗余存储。
时间复杂度低：插入和查询的时间复杂度均为 O(L)（L 为单词长度）。
天然支持前缀搜索，易于扩展通配符功能。

通配符 `.` 的处理逻辑

当搜索遇到 . 时，需要递归遍历当前节点的所有子节点。例如，搜索 app. 时，需检查所有以 app 开头的单词。

三、代码实现（Java）

class WordDictionary {private TrieNode root;public WordDictionary() {root = new TrieNode();}public void addWord(String word) {TrieNode node = root;for (char c : word.toCharArray()) {if (!node.containsKey(c)) {node.put(c, new TrieNode());}node = node.get(c);}node.setEnd(); // 标记单词结束}public boolean search(String word) {return searchHelper(word, 0, root);}private boolean searchHelper(String word, int index, TrieNode node) {if (index == word.length()) {return node.isEnd(); // 检查是否到达单词末尾}char c = word.charAt(index);if (c == '.') {// 遍历所有可能的子节点for (char childChar = 'a'; childChar <= 'z'; childChar++) {if (node.containsKey(childChar) && searchHelper(word, index + 1, node.get(childChar))) {return true;}}return false;} else {// 常规字符匹配return node.containsKey(c) && searchHelper(word, index + 1, node.get(c));}}class TrieNode {private TrieNode[] children = new TrieNode[26];private boolean isEnd;public boolean.containsKey(char c) {return children[c - 'a'] != null;}public TrieNode get(char c) {return children[c - 'a'];}public void put(char c, TrieNode node) {children[c - 'a'] = node;}public void setEnd() {isEnd = true;}public boolean isEnd() {return isEnd;}}
}

四、代码解析

1. TrieNode 类

children 数组：存储 26 个字母对应的子节点。
isEnd 标记：表示该节点是否是单词的结尾。

2. addWord 方法

逐个字符遍历单词，构建字典树结构。
到达单词末尾时，标记 isEnd 为 true。

3. search 方法

递归搜索：从根节点开始，逐个字符匹配。
通配符处理：当遇到 . 时，遍历所有可能的子节点。
终止条件：当遍历完所有字符时，检查当前节点是否为单词结尾。

五、复杂度分析

操作	时间复杂度	空间复杂度
插入单词	O(L)	O(L)
搜索单词	O(L * 26^k)	O (1)（递归栈空间）

L：单词长度。
k：搜索字符串中 . 的数量。

六、示例说明

测试用例：

WordDictionary dict = new WordDictionary();
dict.addWord("apple");
dict.addWord("app");
dict.search("app");      // true
dict.search("app.");     // true（匹配 "apple" 或 "app"）
dict.search("ap..");     // true（匹配 "apple"）
dict.search("apx.");     // false

七、总结

字典树是解决字符串匹配问题的高效工具，结合递归处理通配符，可以优雅地实现本题要求。这种方法在需要频繁进行插入和搜索操作的场景下表现优异，例如拼写检查、自动补全等。

LeetCode 211

实现支持通配符的字典树（Trie）：解决单词匹配问题一、问题描述我们需要设计一个数据结构，支持以下功能： 添加新单词搜索字符串是否与任何已添加的单词匹配，其中搜索字符串可能包含通配符 .（…...

编程日记 2025/7/2 6:01:44

Docker Compose 启动jar包项目

参考文章安装Docker和Docker Compose 点击跳转配置创建一个文件夹存放项目例如mydata mkdir /mydata上传jar包假设我的jar包名称为goudan.jar 编写dockerfile文件 vim app-dockerfile按键盘上的i进行编辑 # 使用jdk8 FROM openjdk:8-jre# 设置时区上海 ENV TZAsia/Sh…...

编程日记 2025/6/30 1:36:37

利用deepseek直接调用其他文生图网站生成图片

这次deepseek输入中文后，其实翻译英文后，是可以丢到比如pollinations.这个网站，来生成图片，用法如下： 你是一个图像生成助手，请根据我的简单描述，想象并详细描述一幅完整的画面。然后将你的详…...

编程日记 2025/6/28 1:24:17

远程装个Jupyter-AI协作笔记本，Jupyter容器镜像版本怎么选？安装部署教程

通过Docker下载Jupyter镜像部署，输入jupyter会发现有几个版本，不知道怎么选？这几个版本有什么差别？ 常见版本有： jupyter/base-notebookjupyter/minimal-notebookjupyter/scipy-notebookjupyter/datascience-notebo…...

编程日记 2025/6/29 8:42:19

11. 盛最多水的容器

leetcode Hot 100系列文章目录一、核心操作二、外层配合操作三、核心模式代码总结一、核心操作最左右两边逐步往中间走，每次在左右中选取小的一个或–记录最大面积提示：小白个人理解，如有错误敬请谅解！ 二、外层配合操作…...

编程日记 2025/6/28 5:38:03

Selenium Web自动化如何快速又准确的定位元素路径，强调一遍是元素路径

如果文章对你有用，请给个赞！ 匹配的ChromeDriver和浏览器版本是更好完成自动化的基础，可以从这里去下载驱动程序： 最全ChromeDriver下载含win linux mac 最新版本134.0.6998.165 持续更新..._chromedriver 134-CSDN博客如果你问…...

编程日记 2025/6/30 20:19:39

Kotlin 基础语法解析

详细的 Kotlin 基础语法解析，结合概念说明和实用场景： --- ### **一、变量与常量** #### **1. 变量类型** - **val**（不可变变量）：声明后不可重新赋值，类似 Java 的 final。 kotlin val name "Kotl…...

编程日记 2025/7/1 17:45:40

html 列表循环滚动，动态初始化字段数据

html <div class"layui-row"><div class"layui-col-md4"><div class"boxall"><div class"alltitle">超时菜品排行</div><div class"marquee-container"><div class"scroll-…...

编程日记 2025/7/2 4:22:20

【大模型基础_毛玉仁】5.4 定位编辑法：ROME

目录 5.4 定位编辑法：ROME5.4.1 知识存储位置1）因果跟踪实验2）阻断实验 5.4.2 知识存储机制5.4.3 精准知识编辑1）确定键向量2）优化值向量3）插入知识 5.4 定位编辑法：ROME 定位编辑：…...

编程日记 2025/6/28 1:24:18

Using SAP an introduction for beginners and business users

Using SAP an introduction for beginners and business users...

编程日记 2025/6/28 1:24:49

Android学习总结之RecyclerView补充篇

在 Android 开发中，列表数据更新的性能一直是关键痛点。传统的 notifyDataSetChanged() 会触发全量刷新，导致不必要的界面重绘。而 DiffUtil 作为 Android 提供的高效差异计算工具，能精准识别数据变化，实现局部更新，成…...

编程日记 2025/6/27 12:08:07

mapbox基础，使用geojson加载cluster聚合图层

👨‍⚕️ 主页： gis分享者 👨‍⚕️ 感谢各位大佬点赞👍 收藏⭐ 留言📝 加关注✅! 👨‍⚕️ 收录于专栏：mapbox 从入门到精通文章目录一、🍀前言1.1 ☘️mapboxgl.Map 地图对象1.2 ☘️mapboxgl.Map style属性1.3 ☘️circle点图层样式二、🍀使用geojson加…...

编程日记 2025/6/27 5:55:09

函数：static和extern

0.前言在正式开始之前先说作用域和生命周期作用域： 作用域有分为局部变量和全局变量局部变量：一个变量仅在其中一段代码内起作用全局变量：所有的代码都可以使用这个变量生命周期： 生命周期是一个代码从运行开始到结束…...

编程日记 2025/6/28 4:04:41

【QT】练习1

1、设计一个颜色选择器，可以输入RGB的颜色值，点击确认，可以把主界面的背景颜色改成设置的颜色修改背景颜色：setStyleSheet(“background-color 红绿蓝颜色值”); // mainwindow.cpp #include "mainwindow.h" #include…...

编程日记 2025/6/28 4:32:28

GreenPlum学习

简介 Greenplum是一个面向数据仓库应用的关系型数据库，因为有良好的体系结构，所以在数据存储、高并发、高可用、线性扩展、反应速度、易用性和性价比等方面有非常明显的优势。Greenplum是一种基于PostgreSQL的分布式数据库，其采用sharednothi…...

编程日记 2025/6/29 9:54:23

张量-pytroch基础（2）

张量-pytroch网站-笔记张量是一种特殊的数据结构，跟数组（array）和矩阵（matrix）非常相似。张量和 NumPy 中的 ndarray 很像，不过张量可以在 GPU 或其他硬件加速器上运行。事实上，张量和 Nu…...

编程日记 2025/6/29 11:38:01

Linux多线程编程的艺术：封装线程、锁、条件变量和信号量的工程实践

目录 📌这篇博客能带给你什么？ 🔥为什么需要封装这些组件？ 一、线程封装框架设计构造与析构 1.线程创建 2.线程分离 3.线程取消 4.线程等待二、锁封装框架设计构造与析构 1.加锁 2.解锁 3.RAII模式三、条件…...

编程日记 2025/6/30 1:36:39

2025年智慧能源与控制工程国际学术会议（SECE 2025）

官网：www.ic-sece.com 简介 2025年智慧能源与控制工程国际学术会议（SECE 2025）将于2025年4月18日线上会议形式召开，这是一个集中探讨全球智慧能源和控制工程领域创新和挑战的国际学术平台。旨在汇集全球领域内的学者、研究人员、…...

编程日记 2025/7/2 4:34:38

Android 16开发实战指南｜锁屏交互+Vulkan优化全解析

一、环境搭建与项目初始化 1. 安装Android Studio Ladybug 下载地址：Android Studio官网关键配置： # 安装后立即更新SDK SDK Manager → SDK Platforms → 安装Android 16 (Preview) SDK Manager → SDK Tools → 更新Android SDK Build-Tools至34.0.0 # 通过命令行安装SDK组…...

编程日记 2025/6/28 3:03:29

sscanf() 用法详解

sscanf() 是 scanf() 的变体，它用于从字符串中提取格式化数据，常用于解析输入字符串。 1️⃣ sscanf() 语法 int sscanf(const char *str, const char *format, ...); str：要解析的字符串（必须是 const char*，可以用…...

编程日记 2025/6/27 8:00:12

0基础入门scrapy 框架，获取豆瓣top250存入mysql

一、基础教程创建项目命令 scrapy startproject mySpider --项目名称创建爬虫文件 scrapy genspider itcast "itcast.cn" --自动生成 itcast.py 文件爬虫名称爬虫网址运行爬虫 scrapy crawl baidu(爬虫名） 使用终端运行太麻烦了，而且…...

编程日记 2025/6/30 17:49:42

Linux常见操作命令（2）

(一）复制和移动复制和移动都分为文件和文件夹，具体的命令是cp和mv。 1.复制文件（复制的文件要是已创建） 格式：cp 源文件目标文件。示例：把filel.txt复制一份得到file2.txt。那么对应的命令就是&#x…...

编程日记 2025/6/30 16:56:54

谷歌将 Android OS 完全转变为 “内部开发”

2025 年 3 月 27 日，据 Android Authority 报道，谷歌证实将从下周开始完全在内部分支机构闭门开发安卓操作系统。相关信息如下： 背景：多年来，谷歌同时维护着两大安卓主要分支，一是面向公众开放的 “安卓开源…...

编程日记 2025/6/28 1:29:31

移动端六大语言速记：第2部分 - 控制结构

移动端六大语言速记：第2部分 - 控制结构本文继续对比Java、Kotlin、Flutter(Dart)、Python、ArkTS和Swift这六种移动端开发语言的控制结构，帮助开发者快速掌握各语言的语法差异。 2. 控制结构 2.1 条件语句各语言条件语句的语法对比： …...

编程日记 2025/6/28 5:29:56

【 Vue 2 中的 Mixins 模式】

Vue 2 中的 Mixins 模式在 Vue 2 里，mixins 是一种灵活的复用代码的方式，它能让你在多个组件间共享代码。借助 mixins，你可以把一些通用的选项（像 data、methods、computed 等）封装到一个对象里，然后在多…...

编程日记 2025/6/29 6:01:33

STM32F103_LL库+寄存器学习笔记13 - 梳理外设CAN与如何发送CAN报文（串行发送）

导言 CAN总线因其高速稳定的数据传输与卓越抗干扰性能，在汽车、机器人及工业自动化中被广泛应用。它采用分布式网络结构，实现多节点间实时通信，确保各控制模块精准协同。在汽车领域，CAN总线连接发动机、制动、车身系统&#xff0c…...

编程日记 2025/6/30 1:54:46

DataPlatter：利用最少成本数据提升机器人操控的泛化能力

25年3月来自中科院计算所的论文“DataPlatter: Boosting Robotic Manipulation Generalization with Minimal Costly Data”。视觉-语言-动作 (VLA) 模型在具身人工智能中的应用日益广泛，这加剧对多样化操作演示的需求。然而，数据收集的高成本往往导致…...

编程日记 2025/6/27 15:00:57

受控组件和非受控组件的区别

在 React 中，受控组件（Controlled Components） 和非受控组件（Uncontrolled Components） 是处理表单元素的两种不同方式，它们的核心区别在于数据管理的方式和与 React 的交互模式。受控组件…...

编程日记 2025/7/2 5:01:03

Mhand Pro 多节点动作捕捉手套：一副手套多场景应用

随着动作捕捉技术的发展，动捕手套的出现为虚拟现实交互、VR游戏开发、机器臂/灵巧手遥操作等方面带来了更加便捷可行的方案。广州虚拟动力作为一家在动作捕捉领域深耕多年的公司，基于传感器技术而研发的多节点惯性动作捕捉手套，兼具VR交互与…...

编程日记 2025/6/28 6:22:33

Kafka消息丢失全解析！原因、预防与解决方案

作为一名高并发系统开发工程师，在使用消息中间件的过程中，无法避免遇到系统中消息丢失的问题，而Kafka作为主流的消息队列系统，消息丢失问题尤为常见。在这篇文章中，将深入浅出地分析Kafka消息丢失的各种情况&#xf…...

编程日记 2025/6/28 1:30:32

BERT与Transformer到底选哪个-上部

一、先理清「技术家谱」：BERT和Transformer是啥关系？ 就像「包子」和「面食」的关系——BERT是「Transformer家族」的「明星成员」，而GPT、Qwen、DeepSeek这些大模型则是「Transformer家族」的「超级后辈」。 1.1 BERT：Transfor…...

编程日记 2025/6/27 2:30:40

【Unity】记录TMPro使用过程踩的一些坑

1、打包到webgl无法输入中文，编辑器模式可以，但是webgl不行，试过网上的脚本，还是不行解决方法：暂时没找到 2、针对字体asset是中文时，overflow的效果模式处理奇怪，它会出现除了overflow模式以…...

编程日记 2025/7/1 19:02:06

数据处理的两种范式：深入解析OLTP与OLAP系统

目录前言1. OLTP：业务运作的基石1.1 OLTP的核心定义与价值1.2 OLTP的技术架构特点1.3 OLTP的典型应用场景 2. OLAP：决策支持的大脑2.1 OLAP的基本概念与作用2.2 OLAP的技术实现方式2.3 OLAP的应用实践 3. OLTP与OLAP的对比与融合3.1 核心差异的深度解析…...

编程日记 2025/6/28 1:24:25

本地飞牛NAS快速部署WordPress个人网站并一键上线公网远程访问

文章目录前言1. Docker下载源设置2. Docker下载WordPress3. Docker部署Mysql数据库4. WordPress 参数设置5. 飞牛云安装Cpolar工具6. 固定Cpolar公网地址7. 修改WordPress配置文件8. 公网域名访问WordPress 推荐前些天发现了一个巨牛的人工智能学习网站，通俗…...

编程日记 2025/7/1 8:05:47

windows环境下的cmake使用

创建一个目录testcmake 进入目录创建一个文件main.cpp : #include <iostream> using namespace std; int main(){cout<<"what is going on?"<<endl;return 0; }再创建一个cmakelists.txt set(CMAKE_CXX_STANDARD 20) add_executable(test2 mai…...

编程日记 2025/6/28 3:16:42

多线程(多线程案例)(续~)

目录一、单例模式 1. 饿汉模式 2. 懒汉模式二、阻塞队列 1. 阻塞队列是什么 2. 生产者消费者模型 3. 标准库中的阻塞队列 4. 自实现阻塞队列三、定时器 1. 定时器是什么 2. 标准库中的定时器欢迎观看我滴上一篇关于多线程的博客呀，直达地址&#xf…...

编程日记 2025/6/30 1:34:03

同步SVPWM调制策略的初步学习记录

最近项目需要用到一些同步调制SVPWM相关的内容（现在的我基本都是项目驱动了），因此对该内容进行一定的学习。 1 同步SVPWM调制的背景我们熟知的一些知识是：SVPWM（空间矢量脉宽调制）是一种用于逆变器的调制…...

编程日记 2025/6/30 4:38:27

权重参数矩阵

目录 1. 权重参数矩阵的定义与作用 2. 权重矩阵的初始化与训练 3. 权重矩阵的解读与分析 (1) 可视化权重分布 (2) 统计指标分析 4. 权重矩阵的常见问题与优化 (1) 过拟合与欠拟合 (2) 梯度问题 (3) 权重对称性问题 5. 实际应用示例案例1：全连接网络中的…...

编程日记 2025/6/27 20:24:01

堆叠虚拟化

各厂商叫法不同：思科 VSS 锐捷 VSU 华为 Stack 华三 IRF 虚拟化为一台设备进行管理，从而实现高可靠性。当任意交换机故障时，都能实现设备、链路切换，保护客户业务稳定运行传统的园区网高可靠性技术出现故障时切换时间很难做到毫…...

编程日记 2025/6/29 23:00:06

3.31-4 性能面试题

面试题 1、性能问题的六个特征： （1）、持续缓慢： （2）、随着时间推进越来越慢、 （3）、随着负载增加越来越慢、 （4）、零星挂起或异常错误、 （5…...

编程日记 2025/6/30 9:41:54

2025年最新自动化/控制保研夏令营预推免面试真题分享（东南/浙大/华科清华）

笔者来2021级本科自动化专业，以下部分将介绍我在夏令营以及预推免期间发生经历和问题东南大学自动化学院东南大学： 东南大学面试有一个十分明显的特点，就是极其注重专业课，基本上就是在面试的时候电脑上会有几个文件夹&#x…...

编程日记 2025/7/1 8:10:37

freecad手动装插件 add on

python工作台输入 FreeCAD.ConfigGet("UserAppData") 在返回的地址上新建文件夹：Mod #like /home/chen/snap/freecad/common 进入Mod #like /home/chen/snap/freecad/common/Mod git clone 你要的项目 #like git clone https://github.com/looooo/f…...

编程日记 2025/6/28 1:25:48

mysql 主从搭建步骤

主库： 开启log-bin参数，log-bin 参数修改需要重启服务器 --You can change the server_id value dynamically by issuing a statement like this:SET GLOBAL server_id 2;--to enable binary logging using a log file name prefix of mysql-bin, and c…...

编程日记 2025/6/27 16:47:46

从AI大模型到MCP中台：构建下一代智能服务的核心架构

从AI大模型到MCP中台：构建下一代智能服务的核心架构引言：AI大模型带来的服务重构革命在ChatGPT掀起全球AI热潮的今天，大模型展现出的惊人能力正在重塑整个软件服务架构。但鲜为人知的是，真正决定AI服务成败的不仅是模型本身&a…...

编程日记 2025/6/28 6:09:27

31天Python入门——第18天:面向对象三大特性·封装继承多态

你好，我是安然无虞。文章目录面向对象三大特性1. 封装2. 继承3. 多态4. 抽象基类5. 补充练习面向对象三大特性面向对象编程（Object-Oriented Programming, 简称OOP）有三大特性, 分别是封装、继承和多态.这些特性是面向对象编程的基础, …...

编程日记 2025/6/30 16:14:20

css_z-index属性

z-index 工作原理及层叠上下文（Stacking Context） 在 CSS 中，z-index 主要用于控制元素的堆叠顺序，决定哪些元素显示在上层，哪些元素在下层。它的工作原理涉及层叠上下文（Stacking Context）&a…...

编程日记 2025/6/27 9:19:05

ros2--xacro

什么是xacro 在ROS 2中，Xacro（XML Macros）是一种基于XML的宏语言，专门用于简化URDF（Unified Robot Description Format）文件的编写。它通过宏定义、变量替换和代码复用等功能，让机器人模型的描…...

编程日记 2025/6/27 10:20:06

Nordic 新一代无线 SoC nRF54L系列介绍

目录概述 1 nRF54L系列特点 1.1 内存 1.2 芯片封装 2 增强的多协议支持 3 其他特性 4 nRF54L系列MCU特性 4.1 多协议无线电 4.2 安全性 4.3 存储空间 4.4 工作参数 4.5 调试接口 4.6 外设概述全新 nRF54L 系列的所有三款器件均将 2.4 GHz 无线电和 MCU 功能 (包括…...

编程日记 2025/6/27 9:49:08

力扣HOT100之矩阵：240. 搜索二维矩阵 II

这道题直接暴力AC的，虽然也能过，但是耗时太长了。 class Solution { public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int edge min(matrix.size(), matrix[0].size()) - 1; //先在edge * edge的矩阵中搜索for…...

编程日记 2025/6/30 12:27:37

一个判断A股交易状态的python脚本

最近在做股票数据相关的项目，需要用到判断某一天某个时刻A股的状态，比如休市，收盘，交易中等，发动脑筋想了一下，这个其实还是比较简单的，这里我把实现方法分享给大家。思路当天是否休市对于某…...

编程日记 2025/6/28 1:29:14