用java实现Trie

Question

尝试实现trie，但它显示内存限制超过了。我试图预先形成的操作是insert、Search，并开始并实现这些函数，我已经为它创建了util函数。我试图在leetcode中提交此解决方案，但超出了鞋子内存限制。请查看这段代码，并帮助我理解问题，而且在许多我见过的程序中，他们都保留了count变量，其目的是什么。

class Trie {

    /** Initialize your data structure here. */
   Trie root;
    Trie []links;
    final int r=26;

    public boolean isEnd;

    public Trie() {

          links=new Trie[r];
        root=new Trie();
    }
    public boolean containsKey(char c)
    {
        return links[c-'a']!=null;
    }
    public Trie get(char ch)
    {
        return links[ch-'a'];
    }
    public void put(char ch,Trie node)
    {
        links[ch-'a']=node;
    }
    public void setEnd()
    {
        isEnd=true;
    }
    public boolean isEnd()
    {
        return isEnd;
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        Trie node=root;
        for(int i=0;i<word.length();i++)
        {
            char ch=word.charAt(i);
            if(!node.containsKey(ch))
            {
                node.put(ch,new Trie());
            }
            node=node.get(ch);
        }
        node.setEnd();   
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {           
        Trie node=searchPrefix(word);
      //    Trie node=null;
        return node!=null && node.isEnd();
    }
    public Trie searchPrefix(String word)
    {
        Trie node=root;
        for(int i=0;i<word.length();i++)
        {
            char ch=word.charAt(i);
            if(node.containsKey(ch))
            {
                node=node.get(ch);
            }
            else
                return null;
        }
        return node;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
       Trie node=searchPrefix(prefix);
        //Trie node=null;
        return node!=null;

    }
}

Answer 1

导致OutOfMemory错误的直接原因是Trie的构造函数中存在递归。

public Trie() {
    links=new Trie[r];
    root=new Trie();
}

您是否看到要创建一个Trie，必须创建一个Trie。这将继续下去，直到内存耗尽为止。

尽管如此，我认为您实际上需要稍微重构代码，将现有的功能划分为两个单独的类：Trie (作为一个整体的结构)和一个TrieNode (包含对子TrieNode的引用)。Trie将包含对根TrieNode的引用。

TrieNode类：

class TrieNode
{
    /** Initialize your data structure here. */
    TrieNode[] links;
    final int r = 26;

    public boolean isEnd;

    public TrieNode()
    {
        links = new TrieNode[r];
    }

    public boolean containsKey(char c)
    {
        return links[c - 'a'] != null;
    }

    public TrieNode get(char ch)
    {
        return links[ch - 'a'];
    }

    public void put(char ch, TrieNode node)
    {
        links[ch - 'a'] = node;
    }

    public void setEnd()
    {
        isEnd = true;
    }

    public boolean isEnd()
    {
        return isEnd;
    }
}

Trie类：

class Trie
{
    TrieNode root;

    public Trie()
    {
        root = new TrieNode();
    }

    /** Inserts a word into the trie. */
    public void insert(String word)
    {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++)
        {
            char ch = word.charAt(i);
            if (!node.containsKey(ch))
            {
                node.put(ch, new TrieNode());
            }
            node = node.get(ch);
        }
        node.setEnd();
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word)
    {
        TrieNode node = searchPrefix(word);
        // Trie node=null;
        return node != null && node.isEnd();
    }

    public TrieNode searchPrefix(String word)
    {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++)
        {
            char ch = word.charAt(i);
            if (node.containsKey(ch))
            {
                node = node.get(ch);
            } else
                return null;
        }
        return node;
    }

    /**
     * Returns if there is any word in the trie that starts with the given prefix.
     */
    public boolean startsWith(String prefix)
    {
        TrieNode node = searchPrefix(prefix);
        // Trie node=null;
        return node != null;
    }
}