首页 > 代码库 > lintcode 442实验Trieste

lintcode 442实验Trieste

2024-11-25 07:11:39   203人阅读

描述

实现一个 Trie，包含 insert, search, 和 startsWith 这三个方法。

样例

技术分享

思路

在了解字典树的性质和结构之后，就容易理解这次要求的是与之相似的三个功能：插入，查找，前缀查找。

插入操作：

建立结点pre，复制root。在pre的children[index]存放插入词汇word的第i个字符（用数字0到25表示a~z的26个字母，记作index），依次类推。若当前的children不存在，则建立大小为26的children结点数组。若children结点数组里的第index个TrieNode为空，则放入新的值为word.charAt(i)的TrieNode。然后pre前进到当前结点的children，pre.children[index]，继续循环操作word的下一个字符。直到放入word的最后一个字符以后，修改pre.exist值为true，说明pre之前的分支完整放入了word。

 

查找操作：

同插入一样，复制root到结点pre，然后遍历查找word的每一个字符word.charAt(i)，若循环里某个pre.children[index]不存在，或者word的最后一个字符的exist标记为false，则返回false。否则，循环结束，返回true。

 

前缀查找操作：唯一和查找操作不同的地方，是不要求word的最后一个字符的exist标记为true。只要遍历完String prefix，就返回true。

/**
 * Your Trie object will be instantiated and called as such:
 * Trie trie = new Trie();
 * trie.insert("lintcode");
 * trie.search("lint"); will return false
 * trie.startsWith("lint"); will return true
 */
class TrieNode {
    // Initialize your data structure here.
    boolean exist;
    char ch;
    TrieNode[] children;
    public TrieNode() {
    }
    public TrieNode(char ch) {
    this.ch = ch;
    }
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    public void insert(String word) {
        if (word == null || word.length() == 0) return;
        TrieNode pre = root;
        for (int i = 0; i < word.length(); i++) {
            if (pre.children == null) pre.children = new TrieNode[26];
            int index = word.charAt(i) - ‘a‘;
            if (pre.children[index] == null) {
                pre.children[index] = new TrieNode(word.charAt(i));
            }
            pre = pre.children[index];
            if (i == word.length()-1) pre.exist = true;
        }
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        if (word == null || word.length() == 0) return false;
        TrieNode pre = root;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - ‘a‘;
            if (pre.children == null || pre.children[index] == null) return false;
            if (i == word.length()-1 && pre.children[index].exist == false) return false;
            pre = pre.children[index];
        }
        return true;
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        if (prefix == null || prefix.length() == 0) return false;
        TrieNode pre = root;
        for (int i = 0; i < prefix.length(); i++) {
            int index = prefix.charAt(i) - ‘a‘;
            if (pre.children == null || pre.children[index] == null) return false;
            pre = pre.children[index];
        }
        return true;
    }
}

这次的题有些麻烦，还是在网上查找相关资料才能最终完成这个结果

 

lintcode 442实验Trieste


联系
我们