LeetCode算法题-Find All Anagrams in a String(Java实现)
这是悦乐书的第228次升级,第240篇原创
01 看题和准备
今天详情的是LeetCode算法题中Easy级别的第95题(顺位题号是438)。给定一个字符串s和一个非空字符串p,找到s中p的字谜的所有起始索引。字符串仅由小写英文字母组成,字符串s和p的长度不会大于20,100。输出顺序无关紧要。例如:
输入:s:“cbaebabacd” p:“abc”
输出:[0,6]
说明:
起始索引等于0的子字符串是“cba”,它是“abc”的字谜。
起始索引等于6的子字符串是“bac”,它是“abc”的字谜。
输入:s:“abab”p:“ab”
输出:[0,1,2]
说明:
起始索引等于0的子字符串是“ab”,它是“ab”的字谜。
起始索引等于1的子字符串是“ba”,它是“ab”的字谜。
起始索引等于2的子字符串是“ab”,它是“ab”的字谜。
本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。
02 第一种解法
题目的意思是在s中寻觅由p中字符任意组成的字符串的起始索引。我们可以先将p中的字符及其出现次数存入一个256大小的整型数组,而后使用循环,从s的第一位字符开始,假如从第1位到p的长度位的字符都能匹配,那么就将起始索引增加进list中。
第一,为了屡次使用存有p字符及其出现次数的数组,我们使用Arrays.copyOf方法,每次复制出一个新数组来解决,不影响原数组中的值。
第二,假如当前字符作为起始无法匹配,那么就结束内层循环,进入s下一个字符继续开始。
第三,由于是连续判断p的长度位,所以外层循环的次数控制为s的长度减去p的长度,直接使用s的长度会报下标越界异常。
public List<Integer> findAnagrams(String s, String p) { List<Integer> list = new ArrayList<Integer>(); if (s == null || s.length() == 0 || s.length() < p.length()) { return list; } int[] arr = new int[256]; for (char ch : p.toCharArray()) { arr[ch]++; } int len = p.length(); for (int i=0; i<=s.length()-len; i++) { boolean isMatch = true; int[] arr2 = Arrays.copyOf(arr, 256); for (int j=i; j<i+len; j++) { if (--arr2[s.charAt(j)] < 0) { isMatch = false; break; } } if (isMatch) { list.add(i); } } return list;}03 第二种解法
对于第一种解法,我们可以再简化下,同样是使用256大小的整型数组,但是我们将s也增加进256大小的数组中去。
先从0开始,将p中的字符及其出现次数增加进pArr数组中,同时将s中的前p的长度个字符增加进sArr数组中,进行第一次的比较,假如两数组相同,那么就将索引0增加进list中。接着,开始循环解决s中剩下的字符。
从p的长度开始作为循环的起始索引,往sArr中增加当前字符出现的次数,同时将s中左边字符出现的次数进行移除,即往sArr中增加新数的同时,移除旧数,而后判断两数组能否相等,相等就将起始索引增加进list中。
在本解法中,判断两数组能否相同使用的是Arrays.equals方法。
public List<Integer> findAnagrams2(String s, String p) { List<Integer> list = new ArrayList<Integer>(); if (s == null || s.length() == 0 || s.length() < p.length()) { return list; } int[] pArr = new int[256]; int[] sArr = new int[256]; for(int i=0; i<p.length(); i++){ pArr[p.charAt(i)]++; sArr[s.charAt(i)]++; } if (Arrays.equals(pArr, sArr)) { list.add(0); } for (int j=p.length(); j<s.length(); j++) { ++sArr[s.charAt(j)]; --sArr[s.charAt(j-p.length())]; if (Arrays.equals(pArr, sArr)) { list.add(j-p.length()+1); } } return list;}04 第三种解法
使用双指针。先将p中的字符及其出现次数初始化进256大小的整型数组,而后定义三个变量,第一个指针从0开始,表示从左,第二个指针也从0开始,表示向右,第三个变量为count,初始值为p的长度。
每次进入循环时,都将右指针向前移动1个单位,假如当前s中的字符存在于数组中,count减1,假如count等于0,则表示已经找到了s中满足p长度的字符串,此时就将左指针增加进list中。假如右指针减去左指针的大小等于p的长度,说明已经判断完一个p长度的字符串了,就需要将左指针往前移动一个单位,并且左指针指向的字符存在于数组中,count加1,最后返回list。
public List<Integer> findAnagrams3(String s, String p) { List<Integer> list = new ArrayList<Integer>(); if (s == null || s.length() == 0 || s.length() < p.length()) { return list; } int[] arr = new int[256]; for (char ch : p.toCharArray()) { arr[ch]++; } int left = 0, right = 0, count = p.length(); while (right < s.length()) { if (arr[s.charAt(right++)]-- >= 1) { count--; } if (count == 0) { list.add(left); } if (right - left == p.length() && arr[s.charAt(left++)]++ >= 0) { count++; } } return list;}05 小结
算法专题目前已连续日更超过两个月,算法题文章95+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。
以上就是一律内容,假如大家有什么好的解法思路、建议或者者其余问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » LeetCode算法题-Find All Anagrams in a String(Java实现)