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] = @"***";
}