java - 操作 trie 实现以获取数组中找到的项目

Question

我从 Code Review 中找到了这个 trie 实现，它工作得很好，我已经以某种方式更改了它以满足我的程序的需求，现在我想操作 find() 函数，这样我就可以得到结果数组。 谢谢。 这是类代码:

import java.util.Collection;
import java.util.HashMap;
import java.util.Map;

public class AutoComplete {

private final Map<Character, HashMap> root = new HashMap<Character, HashMap>();
private final Character END_CHARACTER = '$';

/**
 * Will create an empty AutoComplete
 */
public AutoComplete() {}

/**
 * Will create an AutoComplete filled from a Collection of String items
 *
 * @param items A Collection (Vector, List etc.) of String items
 */
public AutoComplete (Collection<String> items)
{
    for (String s : items)
    {
        internalAdd(s);
    }
}
/**
 * Will create an AutoComplete filled from an array of String items
 *
 * @param items An array of String items
 */
public AutoComplete (String[] items)
{
    for (String s : items){
        internalAdd(s);
    }
}

/**
 * Will add a String to the AutoComplete
 *
 * @param item The String item to add
 * @return Returns true if item is added, false if item already exists
 */
public boolean add(String item)
{
    if (find(item) != null)
    {
        internalAdd(item);
        return true;
    }
    else
    {
        return false;
    }
}

/**
 * Will return an array of Strings that start with the given prefix
 *
 * @param prefix The prefix to search for
 * @return An array of Strings starting with the prefix. Will return null if nothing is found.
 */
public String[] find(String prefix)
{
    Map<Character, HashMap> node = root;

    for (int i = 0; i < prefix.length(); i++)
    {
        if (node.isEmpty())
        {
            return null;
        }
        Character character = prefix.charAt(i);
        if (node.containsKey(character))
        {
            node = node.get(character);
        }
        else
        {
            return null;
        }
    }
    // return found items as an array
}

private boolean internalAdd(final String s)
{
    Map<Character, HashMap> node = root;

    for (int i = 0; i < s.length(); i++)
    {
        Character character = s.charAt(i);
        if(node.isEmpty() || !node.containsKey(character))
        {
            internalAdd(s.substring(i), node);
            break;
        }
        node = node.get(character);
    }
    node.put(END_CHARACTER, new HashMap());
    return true;
}

private void internalAdd(final String s, Map<Character, HashMap> node)
{
    for (int i = 0; i < s.length(); i++)
    {
        Character character = s.charAt(i);
        node.put(character, new HashMap());
        node = node.get(character);
    }
}
}

Answer 1

我更改了整个类，现在它返回数组中找到的项目。这是类代码:

import java.util.ArrayList;
import java.util.Collection;

public class AutoComplete {

private class Node
{
    public int value;
    public Node firstChild;
    public Node nextSibling;

    public Node(int value)
    {
        this.value = value;
        firstChild = null;
        nextSibling = null;
    }
}

public final static char DELIMITER = '\u0001';

private Node root;
private int maxDepth;
private int size;

public AutoComplete()
{
    root = new Node('r');
    size = 0;
}

public AutoComplete (Collection<String> items)
{
    root = new Node('r');
    size = 0;
    for (String item : items)
    {
        if (!isEntry(item))
        {
            add(item);
        }
    }
}

public AutoComplete (String[] items)
{
    root = new Node('r');
    size = 0;
    for (String item : items)
    {
        if (!isEntry(item))
        {
            add(item);
        }
    }
}

public boolean add(String item)
{
    if (isEntry(item))
    {
        return false;
    }
    else if (add(root, item + DELIMITER, 0))
    {
        size++;
        int n = item.length();
        if (n > maxDepth)
        {
            maxDepth = n;
        }
        return true;
    }
    return false;
}

public String[] find(String prefix)
{
    String[] result = suggest(root, prefix, 0);
    if (result[0] == prefix)
    {
        return null;
    }
    else
    {
        return result;
    }
}

private boolean add(Node root, String word, int offset)
{
    if (offset == word.length())
    {
        return false;
    }
    int c = word.charAt(offset);
    Node last = null, next = root.firstChild;
    while (next != null)
    {
        if (next.value < c)
        {
            last = next;
            next = next.nextSibling;
        }
        else if (next.value == c)
        {
            return add(next, word, offset + 1);
        }
        else
        {
            break;
        }
    }

    Node node = new Node(c);
    if (last == null)
    {
        root.firstChild = node;
        node.nextSibling = next;
    }
    else
    {
        last.nextSibling = node;
        node.nextSibling = next;
    }

    for (int i = offset + 1; i < word.length(); i++)
    {
        node.firstChild = new Node(word.charAt(i));
        node = node.firstChild;
    }
    return true;
}

private boolean isEntry(String word)
{
    return isEntry(root, word + DELIMITER, 0);
}

private boolean isEntry(Node root, String word, int offset)
{
    if (offset == word.length())
    {
        return true;
    }
    int c = word.charAt(offset);
    Node next = root.firstChild;
    while (next != null)
    {
        if (next.value < c)
        {
            next = next.nextSibling;
        }
        else if (next.value == c)
        {
            return isEntry(next, word, offset + 1);
        }
        else
        {
            return false;
        }
    }
    return false;
}

private String[] suggest(Node root, String word, int offset)
{
    if (offset == word.length())
    {
        ArrayList<String> words = new ArrayList<String>(size);
        char[] chars = new char[maxDepth];
        for (int i = 0; i < offset; i++)
        {
            chars[i] = word.charAt(i);
        }
        getAll(root, words, chars, offset);
        return words.toArray(new String[words.size()]);
    }
    int c = word.charAt(offset);
    Node next = root.firstChild;
    while (next != null)
    {
        if (next.value < c)
        {
            next = next.nextSibling;
        }
        else if (next.value == c)
        {
            return suggest(next, word, offset + 1);
        }
        else
        {
            break;
        }
    }
    return new String[] { word };
}

private void getAll(Node root, ArrayList<String> words, char[] chars, int pointer)
{
    Node n = root.firstChild;
    while (n != null)
    {
        if (n.firstChild == null)
        {
            words.add(new String(chars, 0, pointer));
        }
        else
        {
            chars[pointer] = (char)n.value;
            getAll(n, words, chars, pointer + 1);
        }
        n = n.nextSibling;
    }
}
}