建设学校网站的需求分析,Joomla外贸网站模板,wordpress4.6,免费网站建设编辑器6.找到字符串中所有的字母异位词
题目:. - 力扣#xff08;LeetCode#xff09;
6.1如何快速判断两个字符串是否是异位词
假设现在有s1 aabca,s2 abaca,那么这两个就是异位词,容易想到的判断方法就是将两个字符串按照字典序排序,再依次比较,但是时间复杂度很高;我们看看…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--,反之则不用 题解: public static ListInteger findAnagrams(String s, String p) {ListInteger 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表需要用MapString,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
题解: class Solution {public ListInteger findSubstring(String s, String[] words) {ListInteger list new ArrayList();MapString,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){MapString,Integer hash2 new HashMap();for(int left i,right i,count 0; right len s.length(); right len){String in s.substring(right,rightlen);hash2.put(in,hash2.getOrDefault(in,0)1);if(hash2.get(in) hash1.getOrDefault(in,0)){count;}if(right-left1 len * m){String out s.substring(left,leftlen);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;}}
