首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode 211. Add and Search Word - Data structure design(字典树)

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

作者头像
ShenduCC
发布2020-02-19 16:40:35
3670
发布2020-02-19 16:40:35
举报
文章被收录于专栏:算法修养算法修养

字典树。

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=0;
        
    }
    
    /** Adds a word into the data structure. */
    void addWord(string word) {
        
        Add(word,0,0);
        
    }
    
    void Add(string word,int i,int pos)
    {
        if(i==word.length())
        {
            tag[pos]=1;
            return;
        }
            
        if(map[pos][word[i]-'a']==0)
        {
            map[pos][word[i]-'a']=++num;
        }
            
        Add(word,i+1,map[pos][word[i]-'a']);
    }
    
    /** 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) {
        
        return  SearchWord(word,0,0);
        
    }
    
    bool SearchWord(string word,int i,int pos)
    {
        if(i==word.length())
        {
            if(tag[pos]==1)
            return true;
            else
            return false;
        }
        
        if(word[i]=='.')
        {
            for(int j=0;j<26;j++)
            {
                if(map[pos][j]!=0)
                {
                   bool ans = SearchWord(word,i+1,map[pos][j]);
                   if(ans==true)
                       return true;
                }
            }
            return false;
        }
        else
        {
            if(map[pos][word[i]-'a']==0)
            {
                return false;
            }
            else
            {
               return SearchWord(word,i+1,map[pos][word[i]-'a']);
            }
        }
      
    }
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary* obj = new WordDictionary();
 * obj->addWord(word);
 * bool param_2 = obj->search(word);
 */
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2020-02-15 ,如有侵权请联系 cloudcommunity@tencent.com 删除

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

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

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档