算法——滑动窗口之找到字符串中所有的字母异位词,串联所有单词的子串

6.找到字符串中所有的字母异位词

题目:. - 力扣（LeetCode）

6.1如何快速判断两个字符串是否是异位词

假设现在有s1 = 'aabca',s2 = 'abaca',那么这两个就是异位词,容易想到的判断方法就是将两个字符串按照字典序排序,再依次比较,但是时间复杂度很高;我们看看下面这种解法:不难发现如果两个字符串为异位词,那么他们之间的相同字符的个数也是相同的,如a有3个,b一个,c一个.那么我们就可以通过判断两个字符串中每种字符的个数是否相同,相同则是异位词,这个功能我们可以利用hash表来实现

6.2解决问题

 s = "cbaebabacd", p = "abc"

暴力解法当然是找出s中的所有长度为p.length 的子串,通过hash来判断是否为异位词,

我们在暴力解法上进行优化:

当我们判断前三个字符后,没必要将right回到b的位置再继续列举,因为实际上我们下一个要判断的是字符串"bae",但是我们在hash2中已经记录了b a的信息,我们只需将c移除hash2,再将a移入hash2即可.这就是滑动窗口的问题,与前面的题目不同的是,这里我们维护的窗口长度是固定的

滑动窗口步骤:

in表示right的元素,out表示left的元素

(1)进窗口 :hash2[in]++

(2)判断如果 right - left + 1 > p.length,那么就要出窗口

(3)出窗口:hash2[out]--

(4)更新结果:判断hash1 和 hash2 字符情况是否相同

在此步骤判断的时候,如果按照上述的步骤来,我们可以建立两个长度为26的数组作为hash表,每次变量两个数组来判断是否相同,加上滑动窗口,时间复杂度为O(26n),即O(n)

这里是因为判断的为单个字符的数量,但是如果题目是要判断字符串的数量呢??

因此我们进行优化:利用count 来统计窗口中"有效字符"的个数

假设我们的字符串为:

我们的步骤是:

在进窗口时:

如此时,在hash2[in] ++之后,我们需要判断hash2[in] 与hash1[in] 的大小关系,如果hash2[in] <= hash1[in],那么说明我们加进来的是一个"有效字符",所谓的有效字符即我们这个字符能低效掉hash1中的某个字符

我们将right++,

此时由于hash2[in] > hash1[in],说明不是一个有效字符,那么count++,同理right再++

为有效字符,count更新为2

我们只需判断count 是否等于 p.length即可,如果相等,那么即为异位词,并且我们这个判断可以穿插在每一次外循环中,因为只有count = p.length才能更新结果

当我们再次right++后,

这时候就要出窗口了,再出窗口时,我们依旧要判断hash2[out] 与hash1[out] 的大小关系,如果hash2[out] <= hash1[out],那么说明我们移出去的是一个"有效字符",那么count--,反之则不用

题解:

java"> public static List<Integer> findAnagrams(String s, String p) {
         List<Integer> ret = new ArrayList<>();
         int[] hash1 = new int[26];
         int[] hash2 = new int[26];
         for(int i = 0; i < p.length(); i++){
             hash1[p.charAt(i) - 'a']++;
         }
         for(int left = 0,right = 0,count = 0; right < s.length(); right++){
             int in = s.charAt(right) - 'a';
             hash2[in]++;
             if(hash2[in] <= hash1[in]){
                 count++;
             }
             if(right - left + 1 > p.length()){
                 int out = s.charAt(left++) - 'a' ;
                 if(hash2[out] <= hash1[out]) {
                     count--;
                 }
                 hash2[out]--;
             }
             if(count == p.length()){
                 ret.add(left);
             }
         }
         return ret;
     }

7.串联所有单词的子串

题目:. - 力扣（LeetCode）

理解题目后,如果我们做过滑动窗口的第6题,就会发现这道题和异位词实际上非常相似,只不过将原先的一个个单词转化为一个个字符串

具体的算法原理在第6题已经说过,我们来看看不同点

(1)哈希表

本题的hash表需要用Map<String,int>来实现

(2)left和right的次数

题目规定,words里面的单词都是等长的,我们记这个长为len,那么我们的left和right每次就都要移动len个字符,以实现跨过一个单词

(3)滑动窗口的执行次数

题目可能会出现"lingmindraboofooowingdingbarrwingmonkeypoundcake" ["fooo","barr","wing","ding","wing"]这样的情况,即left和right可能不是从0下标开始移动的

如上图,我们会发现找不到答案,而事实上还有下面几种可能:

当我们left从m开始的时候,会发现和第一种是一样的,因此我们只需要进行4次,而刚好是执行次数刚好是字符串的长度

也是由于这个问题,我们right的循环结束条件应该为:right + len <= s.length

题解:

java"> class Solution {
     public List<Integer> findSubstring(String s, String[] words) {
         List<Integer> list = new ArrayList<>();
         Map<String,Integer> hash1 = new HashMap<>();
         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<>();
             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){
                     list.add(left);
                 }
             } 
         }
         return list;
     }
 }