LeetCode 438. Find All Anagrams in a String
2020-05-17 19:04:31 # leetcode # string # sliding window

Problem

LeetCode 438. Find All Anagrams in a String

1. 题目简述

给出两个字符串s和p，p非空，找出s中所有p的同字母异序词的索引。例如：

Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

2. 算法思路

sliding window

首先我们能想到的肯定是暴力破解，找出所有的长度和p相等的子串，然后判断是否和p的组成字符一致。可以AC，但是耗时过长，620ms，不太可取，因此尝试别的思路。

如何优化呢？其实我们每次去移动这个子串的时候，其实只移动了一位，剩余的完全没动，但是暴力搜索子串会做很多无意义的计算，因此耗时会变长，所以更加友好的方法应该去计算变化值。

3. 解法

  1. 暴力破解法，很多重复计算
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList();
        if (p.length() > s.length()) {
            return result;
        }

        int s_length = s.length(), p_length = p.length();
        char[] s_array = s.toCharArray();
        int[] src;
        int[] dest = new int[26];

        for (int i = 0; i < p_length; i++) {
            dest[p.charAt(i) - 'a']++;
        }

        for (int i = 0; i < s_length - p_length + 1; i++) {
            src = new int[26];
            for (int j = 0; j < p_length; j++) {
                src[s_array[i + j] - 'a']++;
            }
            int index = 0;
            boolean flag = true;
            while (index < 26 && flag) {
                if (src[index] != dest[index]) {
                    flag = false;
                    break;
                }
                index++;
            }
            if (flag){
                result.add(i);
            }
        }

         return result;
    }
}

  1. 记录变化值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        if (p.length() > s.length()) {
            return new ArrayList<Integer>();
        }

        List<Integer> result = new ArrayList<Integer>();
        int s_length = s.length(), p_length = p.length();
        char[] char_s = s.toCharArray();
        char[] char_p = p.toCharArray();
        int[] arr_s = new int[26], arr_p = new int[26];

        for (int i = 0; i < p_length; i++) {
            arr_s[char_s[i] - 'a']++;
            arr_p[char_p[i] - 'a']++;
        }

        boolean flag = true;
        for (int i = 0; i < 26; i++) {
            if (arr_s[i] != arr_p[i]) {
                flag = false;
                break;
            }
        }
        if (flag) {
            result.add(0);
        }

        int start = 0, end = p_length - 1;
        while (end < s_length - 1) {
            arr_s[char_s[start] - 'a']--;
            start++;
            end++;
            arr_s[char_s[end] - 'a']++;
            flag = true;
            for (int i = 0; i < 26; i++) {
                if (arr_s[i] != arr_p[i]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                result.add(start);
            }
        }

        return result;
    }
}
Prev
2020-05-17 19:04:31 # leetcode # string # sliding window
Next