438.Find All Anagrams in a String

tags: `Medium`,`String`,`Hash Table`,`Sliding Window`

題目描述

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 * 10⁴
s and p consist of lowercase English letters.

解答

C++


















class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> sc(26, 0), pc(26, 0), ans;
        if (s.size() < p.size()) return ans;
        for (int i = 0; i < p.size(); i++) {
            pc[p[i] - 'a']++;
            sc[s[i] - 'a']++;
        }
        if (pc == sc) ans.push_back(0);
        for (int i = p.size(); i < s.size(); i++) {
            sc[s[i] - 'a']++;
            sc[s[i - p.size()] - 'a']--;
            if (pc == sc) ans.push_back(i - p.size() + 1);
        }
        return ans;
    }
};

Yen-Chi ChenSun, Feb 5, 2023

Python











class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        ans = []
        if len(s) < len(p): return ans
        sc, pc = Counter(s[:len(p)]), Counter(p)
        if sc == pc: ans.append(0)
        for i in range(len(p), len(s)):
            sc[s[i]] += 1
            sc[s[i - len(p)]] -= 1
            if sc == pc: ans.append(i - len(p) + 1)
        return ans

Yen-Chi ChenSun, Feb 5, 2023

Javascript







































function findAnagrams(s, p) {
  let left = 0;
  let right = 0;
  let count = p.length;
  const map = [];
  const result = [];

  for (const char of p) {
    if (!map[char]) {
      map[char] = 1;
    } else {
      map[char]++;
    }
  }

  while (right < s.length) {
    if (map[s[right]] > 0) {
      count--;
    }

    map[s[right]]--;
    right++;

    if (count === 0) {
      result.push(left);
    }

    if (right - left === p.length) {
      if (map[s[left]] >= 0) {
        count++;
      }

      map[s[left]]++;
      left++;
    }
  }

  return result;
}

MarsgoatSun, Feb 5, 2023

Reference

回到題目列表