使用 java 实现 Trie

Question

尝试实现 trie，但它显示超出了内存限制。我尝试执行的操作是插入搜索并开始于为了实现这些功能，我为它创建了 util 函数。我试图在 leetcode 中提交这个解决方案，但是鞋子内存限制超出了。请查看这段代码并帮助我理解问题，而且在我看到的许多程序中，它们保持计数变量的目的是什么。

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。这将一直持续到您运行内存不足。

就是说，我认为您实际上需要稍微重组代码，将现有功能分成两个单独的 classes：一个 Trie - 整体结构 - 和一个 TrieNode - 其中包含对子 TrieNode 的引用。 Trie 将包含对根 TrieNode.

的引用

TrieNode class:

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:

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;
    }
}

使用 java 实现 Trie

Implementing Trie using java

java

algorithm

tree

trie

data-structures