LeetCode算法题-Find All Anagrams in a String(Java实现)

作者 : 开心源码 本文共2747个字,预计阅读时间需要7分钟 发布时间: 2022-05-12 共262人阅读

这是悦乐书的第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实现)

发表回复