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

相关文章

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文档的过程中,页边距是一个

Python使用python-docx实现自动化处理Word文档

《Python使用python-docx实现自动化处理Word文档》这篇文章主要为大家展示了Python如何通过代码实现段落样式复制,HTML表格转Word表格以及动态生成可定制化模板的功能,感兴趣的... 目录一、引言二、核心功能模块解析1. 段落样式与图片复制2. html表格转Word表格3. 模板生

Java如何根据word模板导出数据

《Java如何根据word模板导出数据》这篇文章主要为大家详细介绍了Java如何实现根据word模板导出数据,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... pom.XML文件导入依赖 <dependency> <groupId>cn.afterturn</groupId>

Python实现word文档内容智能提取以及合成

《Python实现word文档内容智能提取以及合成》这篇文章主要为大家详细介绍了如何使用Python实现从10个左右的docx文档中抽取内容,再调整语言风格后生成新的文档,感兴趣的小伙伴可以了解一下... 目录核心思路技术路径实现步骤阶段一:准备工作阶段二:内容提取 (python 脚本)阶段三:语言风格调