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

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 res = []
  const sLen = s.length
  const pLen = p.length
  const needMap = new Map()

  for (const letter of p) {
    if (needMap.has(letter)) {
      needMap.set(letter, needMap.get(letter) + 1)
    } else {
      needMap.set(letter, 1)
    }
  }

  const needLen = needMap.size
  const windowMap = new Map()

  let left = 0
  let right = 0
  let meetedLen = 0

  while (right < sLen) {
    const rightLetter = s[right]
    right++

    if (needMap.has(rightLetter)) {
      if (windowMap.has(rightLetter)) {
        windowMap.set(rightLetter, windowMap.get(rightLetter) + 1)
      } else {
        windowMap.set(rightLetter, 1)
      }

      if (windowMap.get(rightLetter) === needMap.get(rightLetter)) {
        meetedLen++
      }
    }

    // 注意这个条件, 因为只有窗口长度等于了 p 的长度
    // 才有可能匹配到异位词, 因此, 当窗口长度大于等于 p 的长度
    // 就到了收缩窗口的时候了
    while (right - left >= pLen) {
      if (meetedLen === needLen) {
        res.push(left)
      }

      const leftLetter = s[left]
      left++

      if (needMap.has(leftLetter)) {
        if (windowMap.get(leftLetter) === needMap.get(leftLetter)) {
          meetedLen--
        }

        windowMap.set(leftLetter, windowMap.get(leftLetter) - 1)
      }
    }
  }

  return res
}

Rust

use std::collections::HashMap;

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

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

    let mut res = Vec::new();
    let need_map_len = need_map.len();
    let mut meeted_count = 0;
    let mut window_map: HashMap<u8, i32> = HashMap::new();
    let (mut start, mut end) = (0, 0);

    while end < s.len() {
        let end_letter = s.as_bytes()[end];
        end += 1;

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

            if window_map.get(&end_letter) == need_map.get(&end_letter) {
                meeted_count += 1;
            }
        }

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

            let start_letter = s.as_bytes()[start];
            start += 1;

            if need_map.contains_key(&start_letter) {
                if window_map.get(&start_letter) == need_map.get(&start_letter) {
                    meeted_count -= 1;
                }

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

    res
}