专栏首页算法修养LeetCode 208. Implement Trie (Prefix Tree)

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;
        
        
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        
        Add(word,0,0);
        
    }
    
    void Add(string word,int i,int pos)
    {
        if(i==word.length())
        {
            return;
        }
            
        if(map[pos][word[i]]==0)
        {
            map[pos][word[i]]=++num;
        }
        
        if(i==word.length()-1)
        {
            tag[pos][word[i]]=1;
        }
        
        Add(word,i+1,map[pos][word[i]]);
    }
    
    
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        
       return SearchWord(word,0,0,1);
        
    }
    
    bool SearchWord(string word,int i,int pos,int t)
    {
        if(i==word.length())
            return false;
       
        if(map[pos][word[i]]==0)
        {
            return false;
        }
        else
        {
            if(i==word.length()-1)
            {
                if(t==1&&tag[pos][word[i]]==1)
                    return true;
                if(t==0)
                    return true;
            }
            
            return SearchWord(word,i+1,map[pos][word[i]],t);
        }
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        return SearchWord(prefix,0,0,0);
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

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

    ShenduCC
  • LeetCode 63. Unique Paths II

    ShenduCC
  • LeetCode 127 Word Ladder

    [题目 LeetCode 127] (https://leetcode.com/problems/word-ladder/description/)

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

    ShenduCC
  • Leetcode 211 Add and Search Word - Data structure design

    Design a data structure that supports the following two operations: void addWor...

    triplebee
  • 干货 | “后 Word Embedding 的”热点会在哪里?

    用户1737318
  • 如何实现拼写纠错功能

    在使用搜索引擎时,当我们输入错误的关键词时,当然这里的错误是拼写错误,搜索引擎的下拉框中仍会显示以正确关键词为前前辍的提示,当你直接回车搜索错误的关键词时,搜索...

    somenzz
  • 无题

    1 月 9 号张小龙在微信之夜上演讲了近 4 个小时,第二天就一堆文字稿出现了,接着是下面这一张图被大量转发

    伪君子
  • 前端笔记,table标签中td宽度不受控制的坑

    在table标签中,td的宽度设置好后,是没有用的,因为table是一个整体,他的td宽度是由其中一个最长td宽度决定的,

    小小鱼儿小小林
  • HanLP《自然语言处理入门》笔记--2.词典分词

    笔记转载于GitHub项目:https://github.com/NLP-LOVE/Introduction-NLP

    mantch

扫码关注云+社区

领取腾讯云代金券