TRANCE

• 1 力扣題208:前綴樹(shù)
• • 1.1 題目描述
  • 1.2 思路分析
  • 1.3 代碼實(shí)現(xiàn)

成都創(chuàng)新互聯(lián)公司企業(yè)建站,十年網(wǎng)站建設(shè)經(jīng)驗(yàn)，專注于網(wǎng)站建設(shè)技術(shù)，精于網(wǎng)頁(yè)設(shè)計(jì)，有多年建站和網(wǎng)站代運(yùn)營(yíng)經(jīng)驗(yàn)，設(shè)計(jì)師為客戶打造網(wǎng)絡(luò)企業(yè)風(fēng)格，提供周到的建站售前咨詢和貼心的售后服務(wù)。對(duì)于成都網(wǎng)站設(shè)計(jì)、網(wǎng)站制作中不同領(lǐng)域進(jìn)行深入了解和探索，創(chuàng)新互聯(lián)在網(wǎng)站建設(shè)中充分了解客戶行業(yè)的需求，以靈動(dòng)的思維在網(wǎng)頁(yè)中充分展現(xiàn)，通過(guò)對(duì)客戶行業(yè)精準(zhǔn)市場(chǎng)調(diào)研，為客戶提供的解決方案。1 力扣題208:前綴樹(shù) 1.1 題目描述

Trie（發(fā)音類似 “try”）或者說(shuō) 前綴樹(shù)
是一種樹(shù)形數(shù)據(jù)結(jié)構(gòu)，用于高效地存儲(chǔ)和檢索字符串?dāng)?shù)據(jù)集中的鍵。這一數(shù)據(jù)結(jié)構(gòu)有相當(dāng)多的應(yīng)用情景，例如自動(dòng)補(bǔ)完和拼寫檢查。

1.2 思路分析

前綴樹(shù)的特點(diǎn)是前綴相同的字符串其樹(shù)的前部分節(jié)點(diǎn)是相同的，構(gòu)造前綴樹(shù)的關(guān)鍵在于一個(gè)節(jié)點(diǎn)表示一個(gè)字母，而子節(jié)點(diǎn)一共有26種可能性，用長(zhǎng)度為26的數(shù)組表示即可。一種可能性為null時(shí)表示無(wú)后繼節(jié)點(diǎn)，一種可能性為node時(shí)還需要加個(gè)節(jié)點(diǎn)標(biāo)記，若標(biāo)記為1表明是終結(jié)字符，可構(gòu)成一個(gè)字符串，否則表明是中間字符，可作為前綴但不可構(gòu)成字符串。關(guān)鍵在于26長(zhǎng)度的數(shù)組和節(jié)點(diǎn)終結(jié)符標(biāo)記

1.3 代碼實(shí)現(xiàn)

private Trie[] children;
    private boolean isEnd;

    public Trie() {children = new Trie[26];
        isEnd = false;
    }
    
    public void insert(String word) {Trie node = this;
        for (int i = 0; i< word.length(); i++) {char ch = word.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }
    
    public boolean search(String word) {Trie node = searchPrefix(word);
        return node != null && node.isEnd;
    }
    
    public boolean startsWith(String prefix) {return searchPrefix(prefix) != null;
    }

    private Trie searchPrefix(String prefix) {Trie node = this;
        for (int i = 0; i< prefix.length(); i++) {char ch = prefix.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {return null;
            }
            node = node.children[index];
        }
        return node;
    }

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

本文題目：2022.12.5前綴樹(shù)-創(chuàng)新互聯(lián)
網(wǎng)頁(yè)URL：http://weahome.cn/article/djgjcd.html