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

Tips

题目类型: 滑动窗口

相关题目:

• 3. 无重复字符的最长子串
• 76. 最小覆盖子串
• 209. 长度最小的子数组
• 239. 滑动窗口最大值
• 424. 替换后的最长重复字符
• 567. 字符串的排列

题目

给定一个字符串 s 和一个非空字符串 p, 找到 s 中所有是 p 的字母异位词的子串, 返回这些子串的起始索引. 字符串只包含小写英文字母, 并且字符串 s 和 p 的长度都不超过 20100.

说明:

字母异位词指字母相同, 但排列不同的字符串. 不考虑答案输出的顺序.

示例

输入: 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" 的字母异位词.

题解

具体题解看 567. 字符串的排列 这道题即可.

JavaScript

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function (s, p) {
  const result = []

  const needMap = new Map()
  for (const ch of p) {
    needMap.set(ch, needMap.has(ch) ? needMap.get(ch) + 1 : 1)
  }

  const windowMap = new Map()
  let metCount = 0
  let start = 0
  let end = 0

  while (end < s.length) {
    const endCh = s[end++]
    if (needMap.has(endCh)) {
      windowMap.set(endCh, windowMap.has(endCh) ? windowMap.get(endCh) + 1 : 1)
      if (windowMap.get(endCh) === needMap.get(endCh)) {
        metCount++
      }
    }

    // 只有窗口长度等于了 p 的长度, 才有可能匹配到异位词, 此时就到了收缩窗口的时候
    while (end - start === p.length) {
      if (metCount === needMap.size) {
        result.push(start)
      }

      const startCh = s[start++]
      if (needMap.has(startCh)) {
        if (windowMap.get(startCh) === needMap.get(startCh)) {
          metCount--
        }
        windowMap.set(startCh, windowMap.get(startCh) - 1)
      }
    }
  }

  return result
}

Rust

use std::collections::HashMap;

pub fn find_anagrams(s: String, p: String) -> Vec<i32> {
    let mut need_map: HashMap<char, i32> = HashMap::new();

    for ch in p.chars() {
        need_map.entry(ch).and_modify(|e| *e += 1).or_insert(1);
    }

    let mut res = Vec::new();
    let mut met_count = 0;
    let mut window_map: HashMap<char, i32> = HashMap::new();
    let (mut start, mut end) = (0, 0);

    while end < s.len() {
        let end_ch = s.chars().nth(end).unwrap();
        end += 1;

        if need_map.contains_key(&end_ch) {
            window_map
                .entry(end_ch)
                .and_modify(|e| *e += 1)
                .or_insert(1);

            if window_map.get(&end_ch) == need_map.get(&end_ch) {
                met_count += 1;
            }
        }

        while end - start >= p.len() {
            if need_map.len() == met_count {
                res.push(start as i32);
            }

            let start_ch = s.chars().nth(start).unwrap();
            start += 1;

            if need_map.contains_key(&start_ch) {
                if window_map.get(&start_ch) == need_map.get(&start_ch) {
                    met_count -= 1;
                }

                window_map.entry(start_ch).and_modify(|e| *e -= 1);
            }
        }
    }

    res
}