算法 字符串 雙指針 2016-03-02
公司要出套Java面試題, 寫到算法處理字符串這段基矮，想起MWS算法，比較有代表性且數(shù)據(jù)結(jié)構(gòu)取巧冠场。
現(xiàn)在把解題思路再梳理一把家浇。
給定一個(gè)字符串S和T，在S中找到一個(gè)最小的子串包含T中的所有字符碴裙，時(shí)間復(fù)雜度為O(n)钢悲。
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
舉例,
S = "ADOBECODEBANC"
T = "ABC"
最小子串是"BANC".
這里有幾個(gè)點(diǎn)需要說明下：
時(shí)間復(fù)雜度是O(n)
其中n是字符串S的長度灌具，因?yàn)槊總€(gè)字符在維護(hù)窗口的過程中不會(huì)被訪問多于兩次。
空間復(fù)雜度則是O(1)
也就是代碼中T的長度譬巫。
數(shù)據(jù)結(jié)構(gòu)選擇
記錄字母出現(xiàn)次數(shù)的數(shù)據(jù)結(jié)構(gòu)有采用哈希Map的也有采用數(shù)組的咖楣，這里介紹一下數(shù)組的用法，因?yàn)樗昧吮容^取巧的方式芦昔。
大小寫字母的ASCII碼不大于128诱贿，這樣array['A']=3指A出現(xiàn)3次，array['B']=1指B出現(xiàn)了一次咕缎，以此類推珠十，不能用常規(guī)意義上的定義array[0]=3表示A出現(xiàn)3次，這樣就多了一層映射凭豪！故而數(shù)組的長度設(shè)置為128即可存放所有的字母焙蹭。明白了么？
算法思想：
- 首先預(yù)處理T嫂伞，用一個(gè)128長 (示例代碼用了256) 的整數(shù)數(shù)組srcHash存儲(chǔ)里面每個(gè)目標(biāo)字符出現(xiàn)的個(gè)數(shù)
- 然后處理原串S孔厉，也用一個(gè)128長的整數(shù)數(shù)組destHash記錄原串字符出現(xiàn)的個(gè)數(shù)。給定兩個(gè)指針start和end帖努，作為最小窗口的左右邊界撰豺。具體實(shí)現(xiàn)看下代碼一目了然。
public class Solution {
public String minWindow(String S, String T) {
int[] srcHash = new int[255];
// 記錄目標(biāo)字符串每個(gè)字母出現(xiàn)次數(shù)
for(int i = 0; i < T.length(); i++){
srcHash[T.charAt(i)]++;
}
int start = 0,i= 0;
// 用于記錄窗口內(nèi)每個(gè)字母出現(xiàn)次數(shù)
int[] destHash = new int[255];
int found = 0;
int begin = -1, end = S.length(), minLength = S.length();
for(start = i = 0; i < S.length(); i++){
// 每來一個(gè)字符給它的出現(xiàn)次數(shù)加1
destHash[S.charAt(i)]++;
// 如果加1后這個(gè)字符的數(shù)量不超過目標(biāo)串中該字符的數(shù)量拼余，則找到了一個(gè)匹配字符
if(destHash[S.charAt(i)] <= srcHash[S.charAt(i)]) found++;
// 如果找到的匹配字符數(shù)等于目標(biāo)串長度污桦，說明找到了一個(gè)符合要求的子串
if(found == T.length()){
// 將開頭沒用的都跳過，沒用是指該字符出現(xiàn)次數(shù)超過了目標(biāo)串中出現(xiàn)的次數(shù)匙监，并把它們出現(xiàn)次數(shù)都減1
while(start < i && destHash[S.charAt(start)] > srcHash[S.charAt(start)]){
destHash[S.charAt(start)]--;
start++;
}
// 這時(shí)候start指向該子串開頭的字母凡橱，判斷該子串長度
if(i - start < minLength){
minLength = i - start;
begin = start;
end = i;
}
// 把開頭的這個(gè)匹配字符跳過，并將匹配字符數(shù)減1
destHash[S.charAt(start)]--;
found--;
// 子串起始位置加1亭姥，我們開始看下一個(gè)子串了
start++;
}
}
// 如果begin沒有修改過稼钩，返回空
return begin == -1 ? "" : S.substring(begin,end + 1);
}
}
加深理解：
解題思路其實(shí)就是通過雙指針維持一個(gè)Window，窗口右指針向右擴(kuò)張用來找到包含子串為目的致份，窗口左指針向右收縮以使子串最小变抽。
典型的滑動(dòng)窗口方法的實(shí)現(xiàn)。
