前言

博主介紹：?目前全網(wǎng)粉絲2W+，csdn博客專家、Java領(lǐng)域優(yōu)質(zhì)創(chuàng)作者，博客之星、阿里云平臺優(yōu)質(zhì)作者、專注于Java后端技術(shù)領(lǐng)域。

涵蓋技術(shù)內(nèi)容：Java后端、算法、分布式微服務(wù)、中間件、前端、運維、ROS等。

博主所有博客文件目錄索引：博客目錄索引(持續(xù)更新)

視頻平臺：b站-Coder長路

LeetCode、208. 實現(xiàn) Trie (前綴樹)【中等，自定義數(shù)據(jù)結(jié)構(gòu)】

題目鏈接與分類

題目鏈接：LeetCode、208. 實現(xiàn) Trie (前綴樹)

分類：02數(shù)據(jù)結(jié)構(gòu)/樹/字典樹(前綴樹)

思路

思路：數(shù)組來模擬前綴樹，對于相同的前綴統(tǒng)一使用一份來存儲。在代碼中使用了通用的代碼：searchPrefix，用于去查找單詞的前綴。

復(fù)雜度分析：

• 初始化：時間復(fù)雜度O(1)；空間復(fù)雜度O(S，字符串長度)
• 其他操作：時間復(fù)雜度O(S，字符串長度)；空間復(fù)雜度O(S，字符串長度)

class TrieNode {
    boolean isWord = false;
    TrieNode[] children = new TrieNode[26];
    public TrieNode(){}
}

class Trie {
    
    TrieNode root;

    public Trie() {
        root = new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode curr = root;
        for (char c : word.toCharArray()) {
            if (curr.children[c - 'a'] == null) curr.children[c - 'a'] = new TrieNode();
            curr = curr.children[c - 'a'];
        }
        curr.isWord = true;
    }
    
    public boolean search(String word) {
        TrieNode node = searchPrefix(word);
        return node != null && node.isWord;
    }
    
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    //通用方法
    public TrieNode searchPrefix(String prefix) {
        TrieNode node = this.root;
        for (char ch: prefix.toCharArray()) {
            int index = ch - 'a';
            if (node.children[index] == null) return null;
            node = node.children[index];
        }
        return node;
    }

}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

資料獲取

大家點贊、收藏、關(guān)注、評論啦~

精彩專欄推薦訂閱：在下方專欄????

• 長路-文章目錄匯總（算法、后端Java、前端、運維技術(shù)導(dǎo)航）：博主所有博客導(dǎo)航索引匯總
• 開源項目Studio-Vue—校園工作室管理系統(tǒng)(含前后臺，SpringBoot+Vue)：博主個人獨立項目，包含詳細(xì)部署上線視頻，已開源
• 學(xué)習(xí)與生活-專欄：可以了解博主的學(xué)習(xí)歷程
• 算法專欄：算法收錄

更多博客與資料可查看????獲取聯(lián)系方式????，??文末獲取開發(fā)資源及更多資源博客獲取??

整理者：長路 時間：2024.2.12文章來源地址http://www.zghlxwxcb.cn/news/detail-827715.html

到了這里，關(guān)于LeetCode、208. 實現(xiàn) Trie (前綴樹)【中等，自定義數(shù)據(jù)結(jié)構(gòu)】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！