Реализация Tr ie с использованием java - PullRequest
Новая
       81

Реализация Tr ie с использованием java

0 голосов
/ 21 апреля 2020

Пытался реализовать tr ie, но он показывает превышение лимита памяти. Операции, которые я пытался выполнить, - это вставка поиска и запуск с, и для реализации этих функций я создал для него функции 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;

    }
}

1 Ответ

0 голосов
/ 21 апреля 2020

Непосредственной причиной вашей ошибки OutOfMemory является то, что у вас есть рекурсия в конструкторе вашего Trie: 

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

Видите ли вы, что для создания Trie вам нужно создать Trie. Это будет продолжаться до тех пор, пока у вас не закончится память.

Тем не менее, я думаю, что вам действительно нужно немного реструктурировать свой код, разделив существующую функциональность на два отдельных класса: Trie - структура как целое - и TrieNode - которое содержит ссылки на дочерние TrieNode s. Trie будет содержать ссылку на root 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;
    }
}
...