我的工作是自动完成的脚本，并想使用一个线索。我的问题是我想匹配要返回的一切。因此，例如我输入信研究我希望所有开头的条目研究要返回。然后开始重等所有项目是否可行有线索，以及如何将它的工作。此外，如果有更好的办法，我愿意接受建议。我想问的原因是它似乎将是复杂和一大堆的处理返回所有节点的客说研究分支。

I am working on an autocompletion script and was thinking about using a trie. My problem is I want everything that matches to be returned. So for example I type in the letter r I want all entries starting with r to be returned. Then all entries starting with re etc. Is this feasible with a trie and how would it work. Also, if there is a better way I am open to suggestions. The reason I ask is it seems like it would be complicated and a whole lot of processing to return all of the nodes off of say the r branch.

是的，我可能会重新发明轮子，但我想了解它是如何工作的。

And yes I may be reinventing the wheel, but I would like to learn how it works.

推荐答案

您完全可以利用特里做到这一点。下面是一些code我扔在一起，可以在正确的方向指向你：

You can absolutely do it using a trie. Here is some code I threw together that can point you in the right direction:

var tokenTree = function (tokenArray) {
var characterArray = "A,B,C,D,E,F,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z".split(',');
var createLetterObject = function (l) {
var pChildren = [];

var getMatchingWords = function (characterArr, availableWords, children) {
    if(characterArr.length == 0){
        for(var child in children){
            var currentChild = children[child];

            var words = currentChild.getWords(characterArr);

            for(var pos in words)
            {
                availableWords.push(words[pos]);
            }

            if(currentChild.word){
                availableWords.push(currentChild.word);
            }
        }
    }
    else
    {
        var currentCharacter = characterArr.pop();
        getMatchingWords (characterArr, availableWords, children[currentCharacter].children);
    }
}

    function doGetWords (wordPart){
        var len = wordPart.length;
        var ar = [];
        var wordList = [];

        for(var ii = len -1; ii >= 0; ii --)
        {
            ar.push(wordPart[ii].toUpperCase());
        }

        getMatchingWords(ar, wordList, pChildren);

        return wordList;
    }

    return {
                letter : l,
                children : pChildren,
                parent : null,
                word : null,

                getWords : doGetWords
        }
}

var startingPoint = createLetterObject ();

function parseWord (wordCharacterArray, parent, fullWord){
    if(wordCharacterArray.length == 0){
        parent.word = fullWord;
        return;
    }

    var currentCharacter = wordCharacterArray.pop().toUpperCase();

    if(!parent.children[currentCharacter]){
        parent.children[currentCharacter] = createLetterObject(currentCharacter);
    }

    parseWord(wordCharacterArray, parent.children[currentCharacter], fullWord);
}

for(var counter in tokenArray){
    var word = tokenArray[counter];

    var ar = [];

    var wordLength = word.length;

    for(var ii = wordLength - 1; ii >= 0; ii--)
    {
        ar.push(word[ii]);
    }

    parseWord(ar, startingPoint, word);
}

    return startingPoint; 
}

......

.....

var tokens = ["Token", "words", "whohaa", "mommy", "test", "wicked"];
var tree = tokenTree(tokens);
var list = tree.getWords(currentTokenSet); //currentTokenSet = w; 
  //it will return words,whohaa,wicked.

我并不是说这是附近最好的或最有效的方式在任何地方，但它至少应该让你指出正确的方向。

I'm not saying this is anywhere near the best or most efficient way, but it should at least get you pointed in the right direction.