您的位置:首页 > 科技 > 能源 > leetcode 438.找到字符串中所有字母异位词

leetcode 438.找到字符串中所有字母异位词

2024/12/23 21:00:36 来源:https://blog.csdn.net/m0_73917165/article/details/141022421  浏览:    关键词:leetcode 438.找到字符串中所有字母异位词

思路:其实就是用滑动窗口的思想,想象出来一个定长的窗口,在原字符串上进行移动,然后判断这个里面的字母是不是和所给字母全部一样。这个实现可以用循环然后用String的substring来模拟滑动窗口。

还有一个问题在于我们怎么判断窗口里面的字母和参照组的字符串里面的字母就是一样的呢?

有一个惯常的方法,就是把所给匹配的字符串排序,然后再把窗口中的字符进行排序,然后对比它们是不是相同的,这样就能判断了。

Java中的sort运用条件是需要转化字符串数组进行排序,需要注意。

class Solution {public List<Integer> findAnagrams(String s, String p) {int len=p.length();List<Integer>ans=new ArrayList<Integer>();char[]you=p.toCharArray();Arrays.sort(you);String tiaojian=new String(you);for(int i=0;i<s.length()-len+1;i++){String buf=s.substring(i,i+len);char[]arr=buf.toCharArray();Arrays.sort(arr);String res=new String(arr);if(res.equals(tiaojian)){ans.add(i);}}return ans;}
}

思路二:也是滑动窗口的思路,但是不一样的是,我们这里的判断条件不一样了,定义两个数组进行比较,这两个数组一个表示s字符串中滑动窗口的字母频次,另一个则表示p字符串的字母频次。

我们这里用了双指针代表滑动窗口的模拟,当窗口长度为p字符串的长度的时候,我们就进行比较它们两个的频次数组是不是完全一样。如果一样,就说明是,把左指针指向的下标装入结果数组中;不是,就同时移动左指针和右指针一个单位,再次进行比较。

class Solution {public List<Integer> findAnagrams(String s, String p) {int len1=s.length();int len2=p.length();List<Integer>ans=new ArrayList<Integer>();int[]a1=new int[26];int[]a2=new int[26];int l=0,r=0;for(int i=0;i<len2;i++)a2[p.charAt(i)-'a']++;while(r<len1){a1[s.charAt(r)-'a']++;if(r-l+1>len2)a1[s.charAt(l++)-'a']--;if(check(a1,a2))ans.add(l);r++;}return ans;}public boolean check(int[]s1,int[]s2){for(int i=0;i<26;i++){if(s1[i]!=s2[i])return false;}return true;}
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com