1.串联所有单词的子串
给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
- 例如，如果
words = ["ab","cd","ef"]， 那么"abcdef"，"abefcd"，"cdabef"，"cdefab"，"efabcd"， 和"efcdab"都是串联子串。"acdbef"不是串联子串，因为他不是任何words排列的连接。
返回所有串联子串在 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"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。
示例 2：
输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。
示例 3：
输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"] 输出：[6,9,12] 解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。 子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。 子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。 子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。
算法原理
我们随便来看一个例子 输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
我们把bar 看成一个a,foo看成一个b,the看成一个c
这个题的s就可以看成一串 abbacvad
这样这个题就变成一个找出字符串你的异位字符,变成跟我们做的上个题是一样的
这道题我们要熟练的运用容器以及哈希表和List表
这道题我们right-left的长度不能大于words数组的长度,即单词的长度
由于我们不确定从哪里开始是我们想要找的单词的首字母,我们需要遍历单个单词的每个字母如下图所示
我们要对一个单词遍历这个单词的每个字母,所以我们要套两层for循环
第一层for循环就是 for(int i=0;i<len;i++) 表示words单词里面每个单词的长度
1.定义left=i,right=i 还需要定义一个count用来记录单词的数量定义两个哈希表,一个哈希表hash1用来记录words数组里面单词的个数,一个哈希表hash2用来记录s表内的单词,用len表示words单词的长度
2.我们的起始位置是right=i,终止位置时 right+len 每次向后移动都是移动len的长度
3.我们首先需要进窗口,用in来接受进入窗口的单词,然后我们判断进来窗口的单是否在 hash1中存在 存在就count++
3,当我们一直向后判断,当right-left的值>words里面字符的m(m表示单词的个数)*len了 说明此时我们应该出窗口了 在出窗口前我们需要判断出窗口的单词是否存在于hash1表中,存在我们就count--
然后left+len判断下一个单词
4.当count==m 说明此时正是我们要找的子串,我们输出left的值
代码如下
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer>ret=new ArrayList();
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++){
Map<String,Integer>hash2=new HashMap<String,Integer>();
for(int left=i,right=i,count=0;right+len<=s.length();right+=len){
String 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){
String out=s.substring(left,left+len);
if(hash2.get(out)<=hash1.getOrDefault(out,0))count--;
hash2.put(out,hash2.get(out)-1);
left+=len;
}
if(count==m){
ret.add(left);
}
}
}
return ret;
}
}2.最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。 - 如果
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 的子串中， 因此没有符合条件的子字符串，返回空字符串。
程序解法：
1.暴力解法：通过暴力枚举，枚举出所有结果，然后比对所有结果那个子串最短
2.滑动窗口+哈希表
算法原理
这个题我们依旧用滑动窗口来做，并且用数组来模拟哈希表
如图我们有以下的一个字符串，我们要找的是abc的最小子串，
1.我们给字符串和abc串各创建一个数组
int[]hash1=new int[128];
int[] hash2=new int[128];
hash1用来存放abc，hash2用来存放长的字符串
我们来统计hash1中的个数，这里使用统计个数的方式不可取，因为长的字符串中有可能有多个一样的字符，我们就取第一次出现的字符为新的字符,就是取种类的个数
for(char ch:t){
if(hash1[ch]==0)kinds++;
hash1[ch]++;
}2.采用滑动窗口的方式
定义left=0，right=0，count=0；
我们首先进入窗口，进窗口之后判断hash2[right]==hash1[right] 相等就++
int minlen=Integer.MAX_VALUE,begin=-1;
for(int left=0,right=0,count=0;right<ss.length();right++){
char in=s[right];
hash2[in]++;
if(hash1[in]==hash2[in])count++;然后当kind和count相等时 我们更新结果，取出当前right-left+1的值，和开始的值
int minlen=Integer.MAX_VALUE,begin=-1;
while(kinds==count){
if(right-left+1<minlen){
minlen=right-left+1;
begin=left;
}3.更新完结果后我们出窗口
char out=s[left];
left++;
if(hash1[out]==hash2[out]) count--;
hash2[out]--;最后代码如下
class minWindow {
public String minWindow1 (String ss, String tt) {
char s[]=ss.toCharArray();
char t[]=tt.toCharArray();
int[]hash1=new int[128];
int[] hash2=new int[128];
int kinds=0;
for(char ch:t){
if(hash1[ch]==0)kinds++;
hash1[ch]++;
}
int minlen=Integer.MAX_VALUE,begin=-1;
for(int left=0,right=0,count=0;right<ss.length();right++){
char in=s[right];
hash2[in]++;
if(hash1[in]==hash2[in])count++;
while(kinds==count){
if(right-left+1<minlen){
minlen=right-left+1;
begin=left;
}
char out=s[left];
left++;
if(hash1[out]==hash2[out]) count--;
hash2[out]--;
}
}
if(begin==-1)return new String();
else return ss.substring(begin,begin+minlen);
}
public static void main(String[] args) {
minWindow minWindow=new minWindow();
String s="ADOBECODEBANC";
String t="AABC";
String result= minWindow.minWindow1(s,t);
System.out.println(result);
}
}
