国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[LintCode/LeetCode] Implement Trie

付永剛 / 3602人閱讀

摘要:首先,我們應該了解字典樹的性質和結構,就會很容易實現要求的三個相似的功能插入,查找,前綴查找。既然叫做字典樹,它一定具有順序存放個字母的性質。所以,在字典樹的里面,添加,和三個參數。

Problem

Implement a trie with insert, search, and startsWith methods.

Notice

You may assume that all inputs are consist of lowercase letters a-z.

Example
insert("lintcode")
search("code") // return false
startsWith("lint") // return true
startsWith("linterror") // return false
insert("linterror")
search("lintcode) // return true
startsWith("linterror") // return true
Note

首先,我們應該了解字典樹的性質和結構,就會很容易實現要求的三個相似的功能:插入,查找,前綴查找。
既然叫做字典樹,它一定具有順序存放26個字母的性質。另外,為了實現和區別全詞查找和前綴查找,應該有一個標記。所以,在字典樹的class里面,添加ch,existchildren三個參數。

插入操作:建立結點pre,復制root。在prechildren[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。

Solution
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;
    }
}

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/65728.html

相關文章

  • [LintCode/LeetCode] Min Stack/Max Stack

    Problem Implement a stack with min() function, which will return the smallest number in the stack. It should support push, pop and min operation all in O(1) cost. Example push(1)pop() // return 1pus...

    GHOST_349178 評論0 收藏0
  • [LintCode/LeetCode] Wildcard Matching

    摘要:遞歸和動規的方法沒有研究,說一下較為直觀的貪心算法。用和兩個指針分別標記和進行比較的位置,當遍歷完后,若也遍歷完,說明完全配對。當之前出現過,且此時和完全無法配對的時候,就一起退回在和配對過的位置。再將和逐個加繼續比較,并將后移。 Problem Implement wildcard pattern matching with support for ? and *. ? Matche...

    Ethan815 評論0 收藏0
  • [LintCode/LeetCode] Intersection of Two Arrays I &

    摘要:先想到的是,其實也可以,只是需要在遍歷的時候,添加到數組中的數要掉,略微麻煩了一點。在里跑的時候,也要快一點。另一種類似做法的就快的多了。如果是找出所有包括重復的截距呢 Problem Given two arrays, write a function to compute their intersection. Notice Each element in the result m...

    enda 評論0 收藏0
  • [Leetcode] Implement Trie 實現前綴樹

    摘要:壓縮前綴樹其實就是將所有只有一個子節點的節點合并成一個,以減少沒有意義的類似鏈表式的鏈接。然后我們開始遍歷這個前綴樹。 Implement Trie Implement a trie with insert, search, and startsWith methods. Note: You may assume that all inputs are consist of lowe...

    jsliang 評論0 收藏0
  • [LintCode/LeetCode] Flatten Nested List Iterator

    摘要:首先,根據迭代器需要不斷返回下一個元素,確定用堆棧來做。堆棧初始化數據結構,要先從后向前向堆棧壓入中的元素。在調用之前,先要用判斷下一個是還是,并進行的操作對要展開并順序壓入對直接返回。 Problem Given a nested list of integers, implement an iterator to flatten it. Each element is either...

    spacewander 評論0 收藏0

發表評論

0條評論

付永剛

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<