网站建设模板素材,猪八戒包装设计,php7安装 WordPress,新手学做网站下载1. 问题描述
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串#xff0c;则返回空字符串 “” 。
注意#xff1a;
对于 t 中重复字符#xff0c;我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量…1. 问题描述
给你一个字符串 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 的子串中 因此没有符合条件的子字符串返回空字符串。
2. 思路
题目要求寻找最小连续子串那么第一个反应就是用滑动窗口求解。滑动窗口移动思路如下
如果当前滑动窗口内没有涵盖t中的所有字符那么窗口的右侧指针继续向右移动扩大窗口。如果当前滑动窗口内涵盖了t中的所有字符那么窗口的左侧指针可以向右移动缩小窗口寻找最小子串直到滑动窗口内无法涵盖t中的所有字符。
移动思路其实比较容易得到那么还有几个问题
由于t中会有重复字符因此我们应该记录t中各个字符的数量。拿什么记录如何判断当前滑动窗口涵盖了t中的所有字符
我一开始的思路是用HashMap字符当作key个数当作value。把字符串t和当前窗口都用两个Map表示。判断当前滑动窗口涵盖了t中的所有字符就将两个map中的键值对都拿出来一一比较只要当前窗口Map的value都大于等于t字符串那就说明涵盖。但这样有个问题我个人对map的遍历取值操作不太熟悉而且感觉使用Map有点重那么有没有别的数据结构可以代替呢
突然想起来可以用数组而且数组在存放时也可以达到O(1)在这道题和Map似乎没有差别。思路如下
由于本题字符串中只有英文字母因此我可以根据ASCII码建立一个数组数组长度就是’A’ - a’的值。这样每一个字符就有固定对应的存放位置可以保存他出现的次数。还是将字符串t和当前窗口都用两个数组表示。判断当前滑动窗口是否涵盖了t中的所有字符那就只需要对两个数组进行比较当前窗口的数组中的每个位置的元素都应该大于等于t字符串。这个操作就很简单了。
3. 代码
public String minWindow(String s, String t) {//滑动窗口的左指针int left 0;//记录最小字串的长度int minLen 100001;//记录最小子串的起始位置int start 0;//t字符串抽象成的数组保存每一个字符出现的次数int[] tArray new int[58];for(int i 0; i t.length(); i) {tArray[t.charAt(i) - A];}//当前滑动窗口抽象成的数组保存每一个字符出现的次数int[] temp new int[58];for(int right 0; right s.length(); right) {//先将这个字符加入到滑动窗口中temp[s.charAt(right) - A];//如果滑动窗口涵盖了字符串twhile(concludeT(temp, tArray)) {//更新最小子串if(minLen right - left 1) {minLen right - left 1;start left;}//左指针向右移动temp[s.charAt(left) - A]--;left;}}return minLen 100001 ? : s.substring(start, start minLen);}//判断当前滑动窗口是否涵盖了t字符串private Boolean concludeT(int[] temp, int[] tArray) {for(int i 0; i temp.length; i) {if(temp[i] tArray[i]) {return false;}}return true;}
