长春网站制作外包,开发次元世界,新余 网站建站 设计 公司,网站后台管理系统破解1.串联所有单词的子串 给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。 s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
例如#xff0c;如果 words [ab,cd,ef]#xff…1.串联所有单词的子串 给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。 s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
例如如果 words [ab,cd,ef] 那么 abcdef abefcdcdabef cdefabefabcd 和 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 i0;ilen;i) 表示words单词里面每个单词的长度
1.定义lefti,righti 还需要定义一个count用来记录单词的数量定义两个哈希表,一个哈希表hash1用来记录words数组里面单词的个数,一个哈希表hash2用来记录s表内的单词,用len表示words单词的长度
2.我们的起始位置是righti,终止位置时 rightlen 每次向后移动都是移动len的长度
3.我们首先需要进窗口,用in来接受进入窗口的单词,然后我们判断进来窗口的单是否在 hash1中存在 存在就count
3,当我们一直向后判断,当right-left的值words里面字符的m(m表示单词的个数)*len了 说明此时我们应该出窗口了 在出窗口前我们需要判断出窗口的单词是否存在于hash1表中,存在我们就count--
然后leftlen判断下一个单词
4.当countm 说明此时正是我们要找的子串,我们输出left的值 代码如下 class Solution {public ListInteger findSubstring(String s, String[] words) {ListIntegerretnew ArrayList();MapString,Integerhash1new HashMapString,Integer();for(String str:words)hash1.put(str,hash1.getOrDefault(str,0)1);int lenwords[0].length(),mwords.length;for(int i0;ilen;i){MapString,Integerhash2new HashMapString,Integer();for(int lefti,righti,count0;rightlens.length();rightlen){String ins.substring(right,rightlen);hash2.put(in,hash2.getOrDefault(in,0)1);if(hash2.get(in)hash1.getOrDefault(in,0))count;if(right-left1len*m){String outs.substring(left,leftlen);if(hash2.get(out)hash1.getOrDefault(out,0))count--;hash2.put(out,hash2.get(out)-1);leftlen;}if(countm){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[]hash1new int[128];
int[] hash2new int[128];
hash1用来存放abchash2用来存放长的字符串
我们来统计hash1中的个数这里使用统计个数的方式不可取因为长的字符串中有可能有多个一样的字符我们就取第一次出现的字符为新的字符,就是取种类的个数 for(char ch:t){if(hash1[ch]0)kinds;hash1[ch];} 2.采用滑动窗口的方式 定义left0right0count0 我们首先进入窗口进窗口之后判断hash2[right]hash1[right] 相等就 int minlenInteger.MAX_VALUE,begin-1;for(int left0,right0,count0;rightss.length();right){char ins[right];hash2[in];if(hash1[in]hash2[in])count; 然后当kind和count相等时 我们更新结果取出当前right-left1的值和开始的值 int minlenInteger.MAX_VALUE,begin-1;
while(kindscount){if(right-left1minlen){minlenright-left1;beginleft;} 3.更新完结果后我们出窗口 char outs[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[]hash1new int[128];int[] hash2new int[128];int kinds0;for(char ch:t){if(hash1[ch]0)kinds;hash1[ch];}int minlenInteger.MAX_VALUE,begin-1;for(int left0,right0,count0;rightss.length();right){char ins[right];hash2[in];if(hash1[in]hash2[in])count;while(kindscount){if(right-left1minlen){minlenright-left1;beginleft;}char outs[left];left;if(hash1[out]hash2[out]) count--;hash2[out]--;}}if(begin-1)return new String();else return ss.substring(begin,beginminlen);}public static void main(String[] args) {minWindow minWindownew minWindow();String sADOBECODEBANC;String tAABC;String result minWindow.minWindow1(s,t);System.out.println(result);}
}
