Lintcode32MinimumWindowSubstringsolution題解

【題目描述】

創(chuàng)新互聯(lián)專注于企業(yè)成都全網(wǎng)營銷推廣、網(wǎng)站重做改版、瑪納斯網(wǎng)站定制設(shè)計(jì)、自適應(yīng)品牌網(wǎng)站建設(shè)、H5響應(yīng)式網(wǎng)站、商城系統(tǒng)網(wǎng)站開發(fā)、集團(tuán)公司官網(wǎng)建設(shè)、成都外貿(mào)網(wǎng)站建設(shè)公司、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁設(shè)計(jì)等建站業(yè)務(wù)，價(jià)格優(yōu)惠性價(jià)比高，為瑪納斯等各大城市提供網(wǎng)站開發(fā)制作服務(wù)。

Given a string source and a string target, find the minimum window in source which will contain all the characters in target.

Notice:If there is no such window in source that covers all characters in target, return the emtpy string "".If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in source.

給定一個(gè)字符串source和一個(gè)目標(biāo)字符串target，在字符串source中找到包括所有目標(biāo)字符串字母的子串。

注意:如果在source中沒有這樣的子串，返回""，如果有多個(gè)這樣的子串，返回起始位置最小的子串。

【題目鏈接】

http://www.lintcode.com/en/problem/minimum-window-substring/

【題目解析】

可以用窗口型兩個(gè)指針的思路來解決，外層for循環(huán)i = 0 ... n, 內(nèi)層while循環(huán)，條件是j < source.length() 和 !isValid(sourceHash, targetHash)，前者是數(shù)組下標(biāo)邊界，后者是一個(gè)函數(shù)，檢查當(dāng)前窗口中的substring是否包含了目標(biāo)字符串中全部所需的字符，未滿足則繼續(xù)擴(kuò)大窗口j++，同時(shí)更新sourceHash。這里sourceHash，targetHash是整型數(shù)組int[]，因?yàn)锳SCII碼最多256個(gè)，因此用int[]可以作為簡化的HashMap使用，key是char對(duì)應(yīng)的int的值，value則是該char在substring中的出現(xiàn)個(gè)數(shù)。isValid函數(shù)則檢查sourceHash是否全部包含了targetHash，256個(gè)字符一一對(duì)應(yīng)，因此只需一重for循環(huán)，如果sourceHash[i] < targetHash[i]，則說明有字符未滿足條件。

需要注意的是，要設(shè)定一個(gè)輔助變量記錄minStr的長度。

【參考答案】

http://www.jiuzhang.com/solutions/minimum-window-substring/

標(biāo)題名稱：Lintcode32MinimumWindowSubstringsolution題解
分享地址：http://bm7419.com/article22/jjcsjc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供定制開發(fā)、品牌網(wǎng)站建設(shè)、品牌網(wǎng)站制作、網(wǎng)站內(nèi)鏈、ChatGPT、營銷型網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)