目錄

串聯(lián)所有單詞的?串（hard）

題目解析

講解算法原理

編寫代碼

最?覆蓋?串（hard）

題目解析

講解算法原理

編寫代碼

---

串聯(lián)所有單詞的?串（hard）

題目解析

1.題目鏈接：. - 力扣（LeetCode）

2.題目描述

給定?個字符串s和?個字符串數(shù)組words。words中所有字符串?度相同。
s中的串聯(lián)?串是指?個包含words中所有字符串以任意順序排列連接起來的?串。
? 例如，如果words=[)ab),)cd),)ef)]，那
么)abcdef)，)abefcd)，)cdabef)，)cdefab)，)efabcd)，和)efcdab)都是串聯(lián)?串。)acdbef)不是串聯(lián)?串，因為他不是任何words排列的連接。
返回所有串聯(lián)字串在s中的開始索引。你可以以任意順序返回答案。
?例1：
輸?：s=)barfoothefoobarman),words=[)foo),)bar)]輸出：[0,9]
解釋：因為words.length==2同時words[i].length==3，連接的?字符串的?度必須為6。?串)barfoo)開始位置是0。它是words中以[)bar),)foo)]順序排列的連接。
?串)foobar)開始位置是9。它是words中以[)foo),)bar)]順序排列的連接。輸出順序?關(guān)緊要。返回[9,0]也是可以的。
?例2：
輸?：s=)wordgoodgoodgoodbestword),words=[)word),)good),)best),)word)]輸出：[]
解釋：因為words.length==4并且words[i].length==4，所以串聯(lián)?串的?度必須為16。s中沒有?串?度為16并且等于words的任何順序排列的連接。
所以我們返回?個空數(shù)組。
?例3：
輸?：s=)barfoofoobarthefoobarman),words=[)bar),)foo),)the)]輸出：[6,9,12]
解釋：因為words.length==3并且words[i].length==3，所以串聯(lián)?串的?度必須為9。?串)foobarthe)開始位置是6。它是words中以[)foo),)bar),)the)]順序排列的連接。?串)barthefoo)開始位置是9。它是words中以[)bar),)the),)foo)]順序排列的連接。?串)thefoobar)開始位置是12。它是words中以[)the),)foo),)bar)]順序排列的連接。

提?：
1<=s.length<=104
1<=words.length<=5000
1<=words[i].length<=30
words[i]和s由?寫英?字?組成

講解算法原理

解法?（暴?解法）：
算法思路：
如果我們把每?個單詞看成?個?個字?，問題就變成了找到「字符串中所有的字?異位詞」。??就是之前處理的對象是?個?個的字符，我們這?處理的對象是?個?個的單詞。

編寫代碼

c++算法代碼：

class Solution
{
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> ret;unordered_map<string, int> hash1; // 保存 words ??所有單詞的頻次for(auto& s : words) hash1[s]++;int len = words[0].size(), m = words.size();for(int i = 0; i < len; i++) // 執(zhí)? len 次{unordered_map<string, int> hash2; // 維護窗?內(nèi)單詞的頻次for(int left = i, right = i, count = 0; right + len <= s.size(); 
right += len){// 進窗? + 維護 countstring in = s.substr(right, len);hash2[in]++;if(hash1.count(in) && hash2[in] <= hash1[in]) count++;// 判斷if(right - left + 1 > len * m){// 出窗? + 維護 countstring out = s.substr(left, len);if(hash1.count(out) && hash2[out] <= hash1[out]) count--;hash2[out]--;left += len;}// 更新結(jié)果if(count == m) ret.push_back(left);}}return ret;}
};

java算法代碼：

class Solution
{public List<Integer> findSubstring(String s, String[] words) {List<Integer> ret = new ArrayList<Integer>();// 保存字典中所有單詞的頻次Map<String, Integer> hash1 = new HashMap<String, Integer>(); for(String str : words) hash1.put(str, hash1.getOrDefault(str, 0) + 1);int len = words[0].length(), m = words.length;for(int i = 0; i < len; i++) // 執(zhí)?次數(shù){// 保存窗?內(nèi)所有單詞的頻次Map<String, Integer> hash2 = new HashMap<String, Integer>(); for(int left = i, right = i, count = 0; right + len <= s.length(); 
right += len){// 進窗? + 維護 countString in = s.substring(right, right + len);hash2.put(in, hash2.getOrDefault(in, 0) + 1);if(hash2.get(in) <= hash1.getOrDefault(in, 0)) count++; // 判斷if(right - left + 1 > len * m){// 出窗? + 維護 countString out = s.substring(left, left + len);if(hash2.get(out) <= hash1.getOrDefault(out, 0)) count--;hash2.put(out, hash2.get(out) - 1);left += len;}// 更新結(jié)果if(count == m) ret.add(left);}}return ret;}
}

最?覆蓋?串（hard）

題目解析

1.題目鏈接：. - 力扣（LeetCode）

2。題目描述

給你?個字符串s、?個字符串t。返回s中涵蓋t所有字符的最??串。如果s中不存在涵蓋t所有字符的?串，則返回空字符串""。
注意：
對于t中重復字符，我們尋找的?字符串中該字符數(shù)量必須不少于t中該字符數(shù)量。如果s中存在這樣的?串，我們保證它是唯?的答案。
?例1：
輸?：s=)ADOBECODEBANC),t=)ABC)輸出：)BANC)
解釋：
最?覆蓋?串)BANC)包含來?字符串t的*A*、*B*和*C*。?例2：
輸?：s=)a),t=)a)輸出：)a)
解釋：
整個字符串s是最?覆蓋?串。?例3:
輸?:s=)a),t=)aa)輸出:""
解釋:
t中兩個字符*a*均應包含在s的?串中，
因此沒有符合條件的?字符串，返回空字符串。

講解算法原理

解法（滑動窗?+哈希表）：
算法思路：
? 研究對象是連續(xù)的區(qū)間，因此可以嘗試使?滑動窗?的思想來解決。
? 如何判斷當前窗?內(nèi)的所有字符是符合要求的呢？
我們可以使?兩個哈希表，其中?個將?標串的信息統(tǒng)計起來，另?個哈希表動態(tài)的維護窗?內(nèi)字符串的信息。
當動態(tài)哈希表中包含?標串中所有的字符，并且對應的個數(shù)都不?于?標串的哈希表中各個字符的個數(shù)，那么當前的窗?就是?種可?的?案。
算法流程：
a. 定義兩個全局的哈希表： 1 號哈希表 hash1 ?來記錄?串的信息， 2 號哈希表 hash2
?來記錄?標串 t 的信息；
b. 實現(xiàn)?個接?函數(shù)，判斷當前窗?是否滿?要求：
i. 遍歷兩個哈希表中對應位置的元素：
? 如果 t 中某個字符的數(shù)量?于窗?中字符的數(shù)量，也就是 2 號哈希表某個位置?于
1 號哈希表。說明不匹配，返回 false ；
? 如果全都匹配，返回 true 。
主函數(shù)中：
a. 先將 t 的信息放? 2 號哈希表中；
b. 初始化?些變量：左右指針： left = 0，right = 0 ；?標?串的?度： len =?
INT_MAX ；?標?串的起始位置： retleft ；（通過?標?串的起始位置和?度，我們就能找到結(jié)果）
c. 當 right ?于字符串 s 的?度時，?直下列循環(huán)：
i. 將當前遍歷到的元素扔進 1 號哈希表中；
ii. 檢測當前窗?是否滿?條件：
? 如果滿?條件：
? 判斷當前窗?是否變?。如果變?：更新?度 len ，以及字符串的起始位置
retleft ；
? 判斷完畢后，將左側(cè)元素滑出窗?，順便更新 1 號哈希表；
? 重復上?兩個過程，直到窗?不滿?條件；
iii. right++ ，遍歷下?個元素；
d. 判斷 len 的?度是否等于 INT_MAX ：
i. 如果相等，說明沒有匹配，返回空串；
ii. 如果不想等，說明匹配，返回 s 中從 retleft 位置往后 len ?度的字符串。

編寫代碼

c++算法代碼：

class Solution
{
public:string minWindow(string s, string t) {int hash1[128] = { 0 }; // 統(tǒng)計字符串 t 中每?個字符的頻次int kinds = 0; // 統(tǒng)計有效字符有多少種for(auto ch : t)if(hash1[ch]++ == 0) kinds++;int hash2[128] = { 0 }; // 統(tǒng)計窗?內(nèi)每個字符的頻次int minlen = INT_MAX, begin = -1;for(int left = 0, right = 0, count = 0; right < s.size(); right++){char in = s[right];if(++hash2[in] == hash1[in]) count++; // 進窗? + 維護 countwhile(count == kinds) // 判斷條件{if(right - left + 1 < minlen) // 更新結(jié)果{minlen = right - left + 1;begin = left;}char out = s[left++];if(hash2[out]-- == hash1[out]) count--; // 出窗? + 維護 count }}if(begin == -1) return "";else return s.substr(begin, minlen);}
};

java算法代碼：

class Solution {public String minWindow(String ss, String tt) {char[] s = ss.toCharArray();char[] t = tt.toCharArray();int[] hash1 = new int[128]; // 統(tǒng)計字符串 t 中每?個字符的頻次int kinds = 0; // 統(tǒng)計有效字符有多少種for(char ch : t)if(hash1[ch]++ == 0) kinds++;int[] hash2 = new int[128]; // 統(tǒng)計窗?內(nèi)每個字符的頻次int minlen = Integer.MAX_VALUE, begin = -1;for(int left = 0, right = 0, count = 0; right < s.length; right++){char in = s[right];if(++hash2[in] == hash1[in]) count++; // 進窗? + 維護 countwhile(count == kinds) // 判斷條件{if(right - left + 1 < minlen) // 更新結(jié)果{minlen = right - left + 1;begin = left;}char out = s[left++];if(hash2[out]-- == hash1[out]) count--; // 出窗? + 維護 count }}if(begin == -1) return new String();else return ss.substring(begin, begin + minlen);}
}