LeetCode *** 211. Add and Search Word - Data structure design(字典树)

2024-04-21 23:18

本文主要是介绍LeetCode *** 211. Add and Search Word - Data structure design(字典树),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

For example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

Note:
You may assume that all words are consist of lowercase letters a-z.


分析:


代码:

 struct TrieNode {public:TrieNode *next[26];bool isStr = false;TrieNode() {memset(next, 0, sizeof(next));}};class WordDictionary {public:TrieNode *root = new TrieNode();// Adds a word into the data structure.void addWord(string word) {int len = word.length();TrieNode *tmp = root;for (int i = 0; i<len; ++i) {if (tmp->next[word[i] - 'a'] == NULL)tmp->next[word[i] - 'a'] = new TrieNode();tmp = tmp->next[word[i] - 'a'];}tmp->isStr = true;}// Returns if the word is in the data structure. A word could// contain the dot character '.' to represent any one letter.bool search(string word) {if (word.size() == 0)return true;TrieNode *tmp = root;if (word[0] == '.') {bool res = false;for (int i = 0; i<26; ++i)if (tmp->next[i] != NULL)res |= (search(word.substr(1), tmp->next[i]));return res;}if (tmp->next[word[0] - 'a'] == NULL)return false;return search(word.substr(1), tmp->next[word[0] - 'a']);}bool search(string word, TrieNode *tmp) {if (word.size() == 0 && tmp->isStr)return true;if (word.size() == 0 || (word.size() && tmp == NULL))return false;if (word[0] == '.') {bool res = false;for (int i = 0; i<26; ++i)if (tmp->next[i] != NULL)res |= (search(word.substr(1), tmp->next[i]));return res;}if (tmp->next[word[0] - 'a'] == NULL)return false;return search(word.substr(1), tmp->next[word[0] - 'a']);}};

这篇关于LeetCode *** 211. Add and Search Word - Data structure design(字典树)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/924279

相关文章

SpringBoot+EasyPOI轻松实现Excel和Word导出PDF

《SpringBoot+EasyPOI轻松实现Excel和Word导出PDF》在企业级开发中,将Excel和Word文档导出为PDF是常见需求,本文将结合​​EasyPOI和​​Aspose系列工具实... 目录一、环境准备与依赖配置1.1 方案选型1.2 依赖配置(商业库方案)二、Excel 导出 PDF

Python 字典 (Dictionary)使用详解

《Python字典(Dictionary)使用详解》字典是python中最重要,最常用的数据结构之一,它提供了高效的键值对存储和查找能力,:本文主要介绍Python字典(Dictionary)... 目录字典1.基本特性2.创建字典3.访问元素4.修改字典5.删除元素6.字典遍历7.字典的高级特性默认字典

Java docx4j高效处理Word文档的实战指南

《Javadocx4j高效处理Word文档的实战指南》对于需要在Java应用程序中生成、修改或处理Word文档的开发者来说,docx4j是一个强大而专业的选择,下面我们就来看看docx4j的具体使用... 目录引言一、环境准备与基础配置1.1 Maven依赖配置1.2 初始化测试类二、增强版文档操作示例2.

Java操作Word文档的全面指南

《Java操作Word文档的全面指南》在Java开发中,操作Word文档是常见的业务需求,广泛应用于合同生成、报表输出、通知发布、法律文书生成、病历模板填写等场景,本文将全面介绍Java操作Word文... 目录简介段落页头与页脚页码表格图片批注文本框目录图表简介Word编程最重要的类是org.apach

python3如何找到字典的下标index、获取list中指定元素的位置索引

《python3如何找到字典的下标index、获取list中指定元素的位置索引》:本文主要介绍python3如何找到字典的下标index、获取list中指定元素的位置索引问题,具有很好的参考价值,... 目录enumerate()找到字典的下标 index获取list中指定元素的位置索引总结enumerat

HTML5 搜索框Search Box详解

《HTML5搜索框SearchBox详解》HTML5的搜索框是一个强大的工具,能够有效提升用户体验,通过结合自动补全功能和适当的样式,可以创建出既美观又实用的搜索界面,这篇文章给大家介绍HTML5... html5 搜索框(Search Box)详解搜索框是一个用于输入查询内容的控件,通常用于网站或应用程

C#实现将Office文档(Word/Excel/PDF/PPT)转为Markdown格式

《C#实现将Office文档(Word/Excel/PDF/PPT)转为Markdown格式》Markdown凭借简洁的语法、优良的可读性,以及对版本控制系统的高度兼容性,逐渐成为最受欢迎的文档格式... 目录为什么要将文档转换为 Markdown 格式使用工具将 Word 文档转换为 Markdown(.

Python实现自动化Word文档样式复制与内容生成

《Python实现自动化Word文档样式复制与内容生成》在办公自动化领域,高效处理Word文档的样式和内容复制是一个常见需求,本文将展示如何利用Python的python-docx库实现... 目录一、为什么需要自动化 Word 文档处理二、核心功能实现:样式与表格的深度复制1. 表格复制(含样式与内容)2

Python实现一键PDF转Word(附完整代码及详细步骤)

《Python实现一键PDF转Word(附完整代码及详细步骤)》pdf2docx是一个基于Python的第三方库,专门用于将PDF文件转换为可编辑的Word文档,下面我们就来看看如何通过pdf2doc... 目录引言:为什么需要PDF转Word一、pdf2docx介绍1. pdf2docx 是什么2. by

如何Python使用设置word的页边距

《如何Python使用设置word的页边距》在编写或处理Word文档的过程中,页边距是一个不可忽视的排版要素,本文将介绍如何使用Python设置Word文档中各个节的页边距,需要的可以参考下... 目录操作步骤代码示例页边距单位说明应用场景与高级用China编程途小结在编写或处理Word文档的过程中,页边距是一个