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

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
示例 2:
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

用两个数组代替哈希表来记录 s 和 p 中字符出现的次数。然后就可以开始滑动窗口了。

class Solution {
public:
  vector<int> findAnagrams(string s, string p) {
    int m = s.length();
    int n = p.length();
    vector<int> res;
    if (n>m){
      return res;
    }
            
    vector<int> s_cnt(26, 0);
    vector<int> p_cnt(26, 0);

    for(int i=0;i<n;i++){
      s_cnt[s[i]-'a']++;
      p_cnt[p[i]-'a']++;
    }
    if(s_cnt==p_cnt){
      res.push_back(0);
    }
    for(int i=n;i<m;i++){
      s_cnt[s[i-n]-'a']--;
      s_cnt[s[i]-'a']++;
      if(s_cnt==p_cnt){
        res.push_back(i-n+1);
      }
    }
    return res;
  }
};

更新日志

2024/12/13 13:22

查看所有更新日志

• 24fac-prepare interview于 2024/12/13