首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >Trie - 211. Add and Search Word - Data structure design

Trie - 211. Add and Search Word - Data structure design

作者头像
ppxai
发布于 2020-09-23 09:30:19
发布于 2020-09-23 09:30:19
28000
代码可运行
举报
文章被收录于专栏:皮皮星球皮皮星球
运行总次数:0
代码可运行

211. Add and Search Word - Data structure design Design a data structure that supports the following two operations:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
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.

Example:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
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.

思路:

由于这一题的匹配是可以直接使用.代替任意字符,所以可以用一个map存下左右的输入字符串,然后用简单的单个字符的比较来做search,但是这里使用前缀树来做。

代码:

go:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
const R = 26


type WordDictionary struct {
    Children [R]*WordDictionary
    Word bool
}


/** Initialize your data structure here. */
func Constructor() WordDictionary {
    return WordDictionary{}
}


/** Adds a word into the data structure. */
func (this *WordDictionary) AddWord(word string)  {
    cur := this
    for i := 0; i < len(word); i++ {
        c := rune(word[i])
        if cur.Children[c - 'a'] == nil {
            cur.Children[c - 'a'] = &WordDictionary{Children : [R]*WordDictionary{}, Word:false}
        }
        cur = cur.Children[c - 'a']
    }
    cur.Word = true
}


/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
func (this *WordDictionary) Search(word string) bool {
    return searchWord(word, this)
}

func searchWord(word string, node *WordDictionary) bool {
    for i := 0; i < len(word) && node != nil; i++ {
        c := rune(word[i])
        if c != '.' {
            node = node.Children[c - 'a']
        } else {
            temp := node
            for _, children := range temp.Children {
                node = children
                if searchWord(word[i+1:], node) {
                    return true
                }
            }
        }
    }
    return node != nil && node.Word
}


/**
 * Your WordDictionary object will be instantiated and called as such:
 * obj := Constructor();
 * obj.AddWord(word);
 * param_2 := obj.Search(word);
 */
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019年08月26日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
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.
triplebee
2018/01/12
5850
LeetCode 0211 - Add and Search Word - Data structure design
Design a data structure that supports the following two operations:
Reck Zhang
2021/08/11
2470
Leetcode 211: Add and Search Word - Data structure design
https://blog.baozitraining.org/2019/03/leetcode-solution-211-add-and-search.html
包子面试培训
2019/04/30
7480
LeetCode 211. Add and Search Word - Data structure design(字典树)
字典树。 class WordDictionary { public: int map[100005][26]; int tag[100005]; int num; /** Initialize your data structure here. */ WordDictionary() { memset(map,0,sizeof(map)); memset(tag,0,sizeof(tag)); num
ShenduCC
2020/02/19
4140
LeetCode 0212 - Word Search II
Given a 2D board and a list of words from the dictionary, find all words in the board.
Reck Zhang
2021/08/11
2110
golang刷leetcode 字符串(5)添加与搜索单词 - 数据结构设计
search(word) 可以搜索文字或正则表达式字符串,字符串只包含字母 . 或 a-z 。. 可以表示任何一个字母。
golangLeetcode
2022/08/02
1800
LeetCode 211. 添加与搜索单词 - 数据结构设计(Trie树)
void addWord(word) bool search(word) search(word) 可以搜索文字或正则表达式字符串,字符串只包含字母 . 或 a-z 。 . 可以表示任何一个字母。
Michael阿明
2020/07/13
4350
LeetCode 211. 添加与搜索单词 - 数据结构设计(Trie树)
LeetCode 208. Implement Trie (Prefix Tree)
题意:实现一个前缀树 class Trie { public: int map[100005][126]; int tag[100005][126]; int num; /** Initialize your data structure here. */ Trie() { memset(map,0,sizeof(map)); memset(tag,0,sizeof(tag)); num=0;
ShenduCC
2020/02/20
2820
LeetCode 211.添加与搜索单词(数据结构设计) - JavaScript
search(word) 可以搜索文字或正则表达式字符串,字符串只包含字母 . 或 a-z 。 . 可以表示任何一个字母。
心谭博客
2020/04/21
4740
Trie - 208. Implement Trie (Prefix Tree)
Implement a trie with insert, search, and startsWith methods.
ppxai
2020/09/23
5650
Leetcode 212 Word Search II 字典树 + 回溯
Given a 2D board and a list of words from the dictionary, find all words in the board. Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell
triplebee
2018/01/12
5590
添加与搜索单词 - 数据结构设计
请你设计一个数据结构,支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
狼啸风云
2023/12/03
2390
【设计数据结构】Trie 运用题
这是 LeetCode 上的「211. 添加与搜索单词 - 数据结构设计」,难度为「中等」。
宫水三叶的刷题日记
2022/04/07
5250
【设计数据结构】Trie 运用题
Trie - 212. Word Search II
212. Word Search II Given a 2D board and a list of words from the dictionary, find all words in the board.
ppxai
2020/09/23
3940
☆打卡算法☆LeetCode 211. 添加与搜索单词 - 数据结构设计 算法解析
大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。
恬静的小魔龙
2022/09/27
2660
☆打卡算法☆LeetCode 211. 添加与搜索单词 - 数据结构设计  算法解析
golang刷leetcode 经典(10) tire树与ac自动机
query(letter):如果存在某些 k >= 1,可以用查询的最后 k个字符(按从旧到新顺序,包括刚刚查询的字母)拼写出给定字词表中的某一字词时,返回 true。否则,返回 false。
golangLeetcode
2022/08/02
1620
字典树概念与题型解析
这次讲一个不经常被人提起的数据结构 - 字典树,虽说知名度不高,但是这个数据结构可以解决其他数据结构所不能解决,或者是比较难解决的问题,而且性能方面,相对于其他的功能类似的数据结构会更优,文章会从概念与基本实现,性能分析,题型解析三大方向来介绍字典树。
五分钟学算法
2019/10/18
6500
【图解算法】模板+变式——带你彻底搞懂字典树(Trie树)
接下来将对经典的字典树进行代码实现;接着做几个变体题目深入理解字典树的强大;最后回到日常生活,瞧瞧字典树怎样融入到了我们的生活之中 >_<
全栈程序员站长
2022/10/04
1.4K0
【图解算法】模板+变式——带你彻底搞懂字典树(Trie树)
数据结构之Trie字典树
Trie 树,也叫“字典树”或“前缀树”。顾名思义,它是一个树形结构。但与二分搜索树、红黑树等不同的是,Trie 树是一种多叉树,即每个节点可以有 m 个子节点。它是一种专门处理字符串匹配的数据结构,用来解决在一组字符串集合中快速查找某个字符串的问题。
端碗吹水
2021/01/29
8880
golang刷leetcode 字符串(2)搜索推荐系统
给你一个产品数组 products 和一个字符串 searchWord ,products 数组中每个产品都是一个字符串。
golangLeetcode
2022/08/02
2740
相关推荐
Leetcode 211 Add and Search Word - Data structure design
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档