javascript - 使用输入搜索时如何保存上次搜索？

Question

我正在尝试编写一种算法来保存最近搜索的关键字。问题是用户没有触发搜索，而是每次键入内容时都会触发搜索。目前，我正在尝试保存上次搜索的关键字并检查下一个是否以最后一个开头，以便丢弃最后一个。

async _persistSearch(term) {
        const serachLog = await this._getLastSearchedFile()
        console.log("[SEARCH]", serachLog);
        if (Object.keys(serachLog) == 0) {
            serachLog.searches = [term];
            serachLog.lastUpdated = Date.now()
        } else if (term.startsWith(this.lastSearhed)) {
            const toPersist = serachLog.searches.filter((value) => value != this.lastSearhed).push(term);
            serachLog.searches = toPersist;
        } else {
            serachLog.searches.push(term);
        }
        this.lastSearhed = term;
        await writeJSONFile(this.searchesFile, serachLog);
    }

例如输入 [so, som, some, somet, someth,somethi, somethin, something, somethin] 是 [something]

Answer 1

您应该使用Trie(前缀树)来保存搜索到的关键词。假设你只处理小写英文字母，那么每个节点最多可以有 26 个子节点。对于每个新的搜索关键字，调用 startsWith 方法来检查这个新关键字是否是先前关键字的任何前缀。

阅读有关此内容的信息 https://en.wikipedia.org/wiki/Trie如果您需要更多关于为什么应在您的案例中使用 Trie 的解释。

这个数据结构的java实现如下。

class Trie {
    class TrieNode{
        private char c;
        private Map<Character, TrieNode> map;
        private boolean isLeaf;   

        TrieNode() {
            this.map = new HashMap<>();
        }
        TrieNode(char c) {
            this.c = c;
            this.map = new HashMap<>();
        }
    }
    private TrieNode root;
    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode();
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode currNode = root;
        for(int i = 0; i < word.length(); i++) {
            char currChar = word.charAt(i);
            if(!currNode.map.containsKey(currChar)) {
                TrieNode newNode = new TrieNode(currChar);    
                currNode.map.put(currChar, newNode);
                currNode = newNode;
            }
            else {
                currNode = currNode.map.get(currChar);
            }
            if(i == word.length() - 1) {
                currNode.isLeaf = true;
            }
        }
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode currNode = root;
        for(int i = 0; i < word.length(); i++) {
            if(!currNode.map.containsKey(word.charAt(i))) {
                return false;
            }
            currNode = currNode.map.get(word.charAt(i));
            if( i == word.length() - 1 && !currNode.isLeaf) {
                return false;
            }
        }
        return true;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode currNode = root;
        for(int i = 0; i < prefix.length(); i++) {
            if(!currNode.map.containsKey(prefix.charAt(i))) {
                return false;
            }
            currNode = currNode.map.get(prefix.charAt(i));
        }
        return true;        
    }
}