每日一題2018.10.20 LeetCode 76

the description of the algorithm：

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）。

Example:

Input： S = “ADOBECODEBANC”， T = “ABC”

Output： “BANC”

Note:

If there is no such window in S that covers all characters in T， return the empty string

“”

。

the algorithm thought：

這個題目我應該是第二遍做了，雖然有些思路，但還是很多地方有問題，最後看了discussion才做出來。首先碰到這種字串匹配的問題，我們可以直接定義一個128維的陣列，來直接儲存，因為一般問題的字串所包含的字元，在ascll碼裡就只到128。然後我們定義兩個迭代器，先讓end這個迭代器走，然後隨著end的移動，我們記錄是否已經成功匹配了一個答案，如果是我們就讓end停下來，再讓start走，隨著start的移動我們自然的縮減匹配字串的長度，達到最佳化的目的。當start走的時候，忽然發現現在不在匹配字串了，我們就再次讓end走，只到到達盡頭或者是又能夠匹配字串了。最後輸出結果的時候，注意判斷是不是一次都沒有匹配，要是一次都沒有匹配我們就輸出空集。

the algorithm；

class Solution {

public：

string minWindow（string s， string t） {

vector map（128，0）；

for（auto c：t）

map［c］++；

int begin=0，end=0，head=0，length=INT_MAX；

int count=t。size（）；

while（end

if（map［s［end++］］——>0） count——；

while（count==0）{

if（length>end-begin） length=end-（head=begin）；

if（map［s［begin++］］++>=0） count++；

}

}

cout<

return length==INT_MAX？“”：s。substr（head，length）；

}

}；

the algorithm analysis：

雖然這個問題裡面有兩個while迴圈，但是end和begin甚至都沒有遍歷完整的兩次字串，所以我們這個演算法的時間複雜度是O（n）的最後也是擊敗了82％的選手，也還算可以了吧。

唔，今天終於週六了，但是起床的太晚了，好好學習吧，今天加油把vistual studio熟悉一遍，然後把資料結構作業做完，再把留了好久的排序演算法寫完吧。加油。