屏蔽字檢測(cè) Trie樹(shù) 及 復(fù)雜度分析

N: 屏蔽字個(gè)數(shù)。 M:表示組成屏蔽字的字符集的數(shù)量 WL:屏蔽字的最大長(zhǎng)度 L:輸入檢測(cè)語(yǔ)句的長(zhǎng)度
inPut: 句子:我羅是有個(gè)志向的,那天看到特朗普就揍他一頓
words: "特朗普","羅志祥","志向","揍"
relpace: ""
則M = 8, WL = 3, N = 4,L = 21
output: 我羅是有個(gè)
的,那天看到他一頓

----- 普通屏蔽字檢測(cè) -----
時(shí)間復(fù)雜度:O(L * N * WL) ex:21 * 4 * 3 = 264 100 * 300 * 3 = 90000
空間復(fù)雜度: O(1)

----- Trie樹(shù) 屏蔽字檢測(cè) -----
時(shí)間復(fù)雜度: O(N * WL) + 0(L * WL) = O((N + L) *WL) ex:(21 + 4) * 3 = 75。 (100 + 300) * 3 = 1200
空間復(fù)雜度: O(WL * N * M)
由于Dict來(lái)存Node的children節(jié)點(diǎn),單個(gè)字符作為key,這樣子的話Dict里面不需要一開(kāi)始不需要初始化成{M1:Node, M2:Node, ..., Mm:Node}
而是Dict都是空的,只有需要insert進(jìn)入的時(shí)候再懶加載創(chuàng)建,并放進(jìn)去,考慮到最極端的情況,就是N個(gè)word沒(méi)有任何交叉,且長(zhǎng)度都為最大WL,此時(shí)需要
的節(jié)點(diǎn)數(shù)量為:WL * N 故空間復(fù)雜度降低到 WL * N

sentence: abcdefghijklmnopqrstuvwxyz
構(gòu)建一個(gè)trie樹(shù)
for (int i=0; i<L; i++)
step, match = trie.walk(i)
i += step;
if (!match) {
NSLog(@"not match:%@", s[i:i+step]);
} else {
s[i:i+step] = @"***";
}

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成,瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明:文章內(nèi)容(如有圖片或視頻亦包括在內(nèi))由作者上傳并發(fā)布,文章內(nèi)容僅代表作者本人觀點(diǎn),簡(jiǎn)書(shū)系信息發(fā)布平臺(tái),僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容