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

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+篇,