[LeetCode] 438. Find All Anagrams in a String

Given two strings s and p, return an array of all the start indices of p’s anagrams in s. You may return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:
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”.

Example 2:
Input: s = “abab”, p = “ab”
Output: [0,1,2]
Explanation:
The substring with start index = 0 is “ab”, which is an anagram of “ab”.
The substring with start index = 1 is “ba”, which is an anagram of “ab”.
The substring with start index = 2 is “ab”, which is an anagram of “ab”.

Constraints:
1 <= s.length, p.length <= 3 * 104
s and p consist of lowercase English letters.

找到字符串中所有字母异位词。

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-all-anagrams-in-a-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。思路是滑动窗口（sliding window）。这个题也可以用之前的模板做，参见76，159，340。先遍历p，得到 p 中每个字母和他们对应的出现次数。再去遍历 s，用 start 和 end 指针，end 在前，当某个字母的出现次数被减少到 0 的时候，counter 才能–。当 counter == 0 的时候，判断 end - begin 是否等于p的长度，若是，才能将此时 begin 的坐标加入结果集。

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int[] map = new int[256];
        for (char c : p.toCharArray()) {
            map[c]++;
        }
        int counter = p.length();
        
        // corner case
        if (s.length() < p.length()) {
            return res;
        }
        // normal case
        int start = 0;
        int end = 0;
        while (end < s.length()) {
            char c1 = s.charAt(end);
            if (map[c1] > 0) {
                counter--;
            }
            map[c1]--;
            end++;
            while (counter == 0) {
                char c2 = s.charAt(start);
                map[c2]++;
                if (map[c2] > 0) {
                    counter++;
                }
                if (end - start == p.length()) {
                    res.add(start);
                }
                start++;
            }
        }
        return res;
    }
}

JavaScript实现

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
	let res = [];
	if (p.length > s.length) {
		return res;
	}

	let map = new Map();
	for (let c of p) {
		map.set(c, (map.get(c) | 0) + 1);
	}

	let begin = 0,
		end = 0,
		counter = map.size;
	while (end < s.length) {
		let c = s.charAt(end);
		if (map.has(c)) {
			map.set(c, map.get(c) - 1);
			if (map.get(c) === 0) {
				counter--;
			}
		}
		end++;
		while (counter === 0) {
			let d = s.charAt(begin);
			if (map.has(d)) {
				map.set(d, map.get(d) + 1);
				if (map.get(d) > 0) {
					counter++;
				}
			}
			if (end - begin == p.length) {
				res.push(begin);
			}
			begin++;
		}
	}
	return res;
};