題目:
給定一個字符串及一個字符串集合A,求該字符串中包含A中所有字符的最短子串長度。
解決方案一:
最直接的方法就是,直接開始遍歷:查找任意兩個子串之間是否包含str2,如果包含,記錄下長度,求得最小值即可。
str1 = "daebfacba";
str2 = "abc";
minLen = len(str1);
for i = 0:len(str1)
for j = i+1:len(str1)
if (isContainAllElements(str1,str2,i,j)) //如果i到j的子串包含所有字符,則記錄長度
if j-i < minLen
minLen = j-i;
考慮isContainAllElements(),復雜度為O(n3)。
解決方案二:
為str2中的每一個字符設置一個變量,用來存儲最新的在str1中出現的位置。用H(x)來表示該數值。
以“daebfacba”為例,
1. 掃描到第一個a時,H(a)=1; H(b),H(c)無值;
2. 掃描到第一個b時,H(a)=1; H(b)= 3,H(c)無值;
3.掃描到第二個a時,由於C還無值,因此,直接覆蓋a的值:H(a)=5; H(b)=3,H(c)無值;
4. 掃描到第一個c時,H(a)=5; H(b)=3,H(c)=6,此時計算一次距離,即用最大值減去最小值為3;
5.繼續掃描,到第二個b時,H(a)=5; H(b)=7,H(c)=6,此時距離為7-5=2;
6.繼續掃描,到第三個a時,H(a)=8; H(b)=7,H(c)=6,此時距離為8-6=2;
則最小值為2.
該算法復雜度O(n)。
該算法中,在所有字符對應位置未全找到時可以直接覆蓋,能否覆蓋的簡單可行性論證如下:
假設a出現兩次,b和c有三種相對位置可以出現:
(1)a ... b ... a ... c...
此時,第二個a會覆蓋第一個a,但由於c在第二個a後面,因此僅需要計算第二個a就可以了,覆蓋是可以的。
(2)a ... b...c ... a ...
此時,兩個a都會參與計算,不存在覆蓋問題。
(3)a...a...b..c...
此時,顯然可見,只需要計算第二個a,覆蓋是可以的。
因此,總結一下,覆蓋的方法是可行的。
總體思路為:
1. 掃描字符串,如果遇到集合中的字符,則將集合中字符所在位置記錄下來
2. 如果所有字符的位置還有未找到的,直接填充或者覆蓋;
此時,如果都找到了,則計算距離,並於最短距離進行比較;否則,按照上述規則繼續填充;
3. 掃描完字符串即可得到最短子串長度,同時還可以記錄下所有字符的位置。
拓展:
題目:
給定一個字符串及一個字符串集合A,求該字符串中包含A中所有字符的最長子串長度(不允許A中的字符在子串中重復)。www.2cto.com
例如,“ababcda”,“abc”
思路類似,規則如下:
1. 如果各字符對一個的值未填滿時:
(1)當前字符對應值未填,則直接填入;
(2)當前字符對應值已經填充(例如,H(a)=2),則清除a位置2及2之前的已經填充的值,並且重新填入a的值(例如H(a)=4);(因為出現了重復,需要清空前面的)