C# PrefixTree accepted solution


  • 0
    D

    OK, i am a bit puzzled for i literally just resubmitted my exact same code and it passed the TLE on one case .. that's probably OJ C# mono compiler biting .. but anyways .. here it's

    using System.Collections.Generic;
    using System;
    
    internal class PrefixTree
    {
    public char key;
    int childCount = 0;
    bool final = false;
    PrefixTree[] children;
    public PrefixTree(char c)
    {
        key = c;
        children = new PrefixTree[26];
    }
    
    public void Add(string s)
    {
        if(s.Length > 0)
        {
            PrefixTree child = children[s[0] - 'a'];
            if(child != null){
                child.Add(s.Substring(1));
            }
            else
            {
                child = new PrefixTree(s[0]);
                child.Add(s.Substring(1));
                children[s[0] - 'a'] = child;
                childCount ++;
            }
        }else
        {
            final = true;
        }
    }
    
    public bool Find(string p)
    {
        if(p.Length == 0) return final;
        if(p[0] != '.'){
            PrefixTree child = children[p[0] -'a'];
            if(child != null){
                return child.Find(p.Substring(1));
            }
            return false;
        }else
        {
            string np = p.Substring(1);
            foreach(PrefixTree tree in children)
            {
                if(tree != null && tree.Find(np)) return true;
            }
            return false;
        }
       }
    

    }

    public class WordDictionary {
    PrefixTree root = new PrefixTree('$');
    // Adds a word into the data structure.
    public void AddWord(String word) {
        root.Add(word);
    }
    
    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    public bool Search(string word) {
        if(string.IsNullOrEmpty(word)) return false;
        return root.Find(word);
    }
    

    }

    // Your WordDictionary object will be instantiated and called as such:
    // WordDictionary wordDictionary = new WordDictionary();
    // wordDictionary.AddWord("word");
    // wordDictionary.Search("pattern");


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.