azl397985856 commented 2 years ago

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

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/

前置知识

Sliding Window

哈希表

题目描述


给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：

字母异位词指字母相同，但排列不同的字符串。不考虑答案输出的顺序。示例 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" 的字母异位词。

laofuWF commented 2 years ago

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        res = []

        if len(s) < len(p):
            return res

        counter = defaultdict(int)
        for char in p:
            counter[char] += 1
        valid_count = 0
        left = 0

        for right in range(len(s)):
            char = s[right]
            if char in counter:
                counter[char] -= 1
                if counter[char] >= 0:
                    valid_count += 1

            while valid_count == len(p):
                if right - left + 1 == len(p):
                    res.append(left)

                temp = s[left]

                if temp in counter:
                    counter[temp] += 1
                    if counter[temp] > 0:
                        valid_count -= 1
                left += 1

        return res

djd28176 commented 2 years ago


class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        np, ns = len(p), len(s)
        if np > ns:
            return []
        pCounter, sCounter = {},{}

        for i in range(np):
            pCounter[p[i]] = 1 + pCounter.get(p[i],0)
            sCounter[s[i]] = 1 + sCounter.get(s[i],0)

        res = [0] if sCounter == pCounter else []
        l = 0
        for r in range(np, ns):
            sCounter[s[r]] = 1 + sCounter.get(s[r],0)
            sCounter[s[l]] -= 1

            if sCounter[s[l]] <= 0:
                sCounter.pop(s[l])
            l += 1
            if sCounter == pCounter:
                res.append(l)
        return res

lbc546 commented 2 years ago

Python solution

class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        if len(s) < len(p):
            return []

        pcount = collections.Counter(p)
        scount = collections.Counter()
        ans = []

        for i in range(len(s)):
            scount[s[i]] += 1
            if i >= len(p):
                if scount[s[i-len(p)]] == 1:
                    del scount[s[i-len(p)]]
                else:
                    scount[s[i-len(p)]] -= 1

            if pcount == scount:
                ans.append(i-len(p)+1)
        return ans

Complexity

O(n)

yopming commented 2 years ago

// 使用hashmap来存储每个letter的个数，使用sliding window来更新hashmap
// 当 ptr2 - ptr1 >= anagram.size() 时候，更新ptr1，也就是window的左边的自增
// 当 ptr2 也就是window的右边 >= anagram.size() - 1时，检查两个hashmap
// 使用std::unordered_map会比使用std::vector<int>(26,0)慢很多（100倍时间），而且还要额外写compare unordered_map的函数

// Time: O(n)
// Space: O(1) or O(26)

class Solution {
public:
  vector<int> findAnagrams(string s, string p) {
    std::vector<int> map(26,0);
    std::vector<int> anagram_map(26,0);
    for (auto& c: p) {
      anagram_map[c-'a']++;
    }
    
    std::vector<int> results;
    int anagram_size = p.size();
    int start = 0;
    for (int i = 0; i < s.size(); i++) {
      map[s[i]-'a']++;
      if (i - start >= anagram_size) {
        map[s[start++]-'a']--;
      }
      
      if (i >= anagram_size - 1) {
        if (map == anagram_map) {
          results.push_back(start);
        }
      }
    }
    
    return results;
  }
};

thinkfurther commented 2 years ago

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(s) < len(p):
            return []

        result = []
        p_dict = Counter(p)

        s_dict = defaultdict(int)
        for idx in range(len(p)):
            s_dict[s[idx]] += 1        

        if s_dict == p_dict:
            result.append(0)

        left = 0
        for right in range(len(p), len(s)):

            s_dict[s[right]] += 1

            s_dict[s[left]] -= 1
            if s_dict[s[left]] == 0:
                del s_dict[s[left]]
            left += 1

            if s_dict == p_dict:
                result.append(left)

        return result

时间复杂度：O(n) 空间复杂度：O(n)

MichaelXi3 commented 2 years ago

Idea

滑动窗口

Code


class Solution {
public List<Integer> findAnagrams(String s, String p) {
// List that stores results
List<Integer> res = new ArrayList<>();
if (p.length() > s.length()) { return res; } // Impossible case

    // Use Array to store target string info: Char & Frequency
    int[] target = new int[26];
    for (int i = 0; i < p.length(); i++) {
        target[p.charAt(i) - 'a']++;
    }

    // Use Array to store string s info: Char & Frequency
    // Sliding window begins
    int[] window = new int[26];
    for (int i = 0; i < p.length(); i++) {
        window[s.charAt(i) - 'a']++;
    }

    // Compare and see whether the first set of comparsion is valid
    // if (isEqual(window, target)) {res.add(0);}

    // Compare the rest of string s, sliding window begin to slide
    int i = 0;
    while (i <= s.length() - p.length()) {
        if (isEqual(window, target)) {res.add(i);}
        window[s.charAt(i) - 'a']--;
        if (i + p.length() < s.length()) {
            window[s.charAt(i + p.length()) - 'a']++;
        }
        i++;
    }
    return res;
}

private boolean isEqual(int[] arr, int[] target) {
    for (int i = 0; i < target.length; i++) {
        if (arr[i] != target[i]) {
            return false;
        }
    }
    return true;
}

}

Cusanity commented 2 years ago

Idea

Sliding Window

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        HashMap<Character, Integer> need = new HashMap<>();
        for(char ch: p.toCharArray())
            need.put(ch, need.getOrDefault(ch, 0) + 1);
        int left = 0;
        int right = 0;
        int valid = 0;
        int needed = p.length();
        int n = s.length();
        ArrayList<Integer> res = new ArrayList<>();
        while(right < n){
            char curr_ch = s.charAt(right);
            if(need.containsKey(curr_ch)){
                need.put(curr_ch, need.get(curr_ch) - 1);
                if(need.get(curr_ch) >= 0)
                    valid++;
            }
            while(valid == needed){
                if(right - left + 1 == needed)
                    res.add(left);
                char char_removed = s.charAt(left);
                if(need.containsKey(char_removed)){
                    need.put(char_removed, need.get(char_removed) + 1);
                    if(need.get(char_removed) > 0)
                        valid--;
                }
                left++;
            }
            right++;
        }
        return res;
    }
}

Complexity:

Time: O(n)
Space: O(n)

cyang258 commented 2 years ago

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        HashMap<Character, Integer> need = new HashMap<>();
        for(char ch: p.toCharArray())
            need.put(ch, need.getOrDefault(ch, 0) + 1);
        int left = 0;
        int right = 0;
        int valid = 0;
        int needed = p.length();
        int n = s.length();
        ArrayList<Integer> res = new ArrayList<>();
        while(right < n){
            char curr_ch = s.charAt(right);
            if(need.containsKey(curr_ch)){
                need.put(curr_ch, need.get(curr_ch) - 1);
                if(need.get(curr_ch) >= 0)
                    valid++;
            }
            while(valid == needed){
                if(right - left + 1 == needed)
                    res.add(left);
                char char_removed = s.charAt(left);
                if(need.containsKey(char_removed)){
                    need.put(char_removed, need.get(char_removed) + 1);
                    if(need.get(char_removed) > 0)
                        valid--;
                }
                left++;
            }
            right++;
        }
        return res;
    }
}

Time: O(n)

Space: O(n)

steven72574 commented 2 years ago

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length(), pLen = p.length();

        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }

        List<Integer> ans = new ArrayList<Integer>();
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        for (int i = 0; i < pLen; ++i) {
            ++sCount[s.charAt(i) - 'a'];
            ++pCount[p.charAt(i) - 'a'];
        }

        if (Arrays.equals(sCount, pCount)) {
            ans.add(0);
        }

        for (int i = 0; i < sLen - pLen; ++i) {
            --sCount[s.charAt(i) - 'a'];
            ++sCount[s.charAt(i + pLen) - 'a'];

            if (Arrays.equals(sCount, pCount)) {
                ans.add(i + 1);
            }
        }

        return ans;
    }
}

phoenixflyingsky commented 2 years ago

public List findAnagrams(String s, String p) {

List<Integer> res = new LinkedList<>();
if (s == null || p == null || s.length() < p.length())
    return res;

int[] ch = new int[26];
//统计p串字符个数
for (char c : p.toCharArray())
    ch[c - 'a']++;
//把窗口扩成p串的长度
int start = 0, end = 0, rest = p.length();
for (; end < p.length(); end++) {
    char temp = s.charAt(end);
    ch[temp - 'a']--;
    if (ch[temp - 'a'] >= 0)
        rest--;
}

if (rest == 0)
    res.add(0);
//开始一步一步向右移动窗口。
while (end < s.length()) {
    //左边的拿出来一个并更新状态
    char temp = s.charAt(start);
    if (ch[temp - 'a'] >= 0)
        rest++;
    ch[temp - 'a']++;
    start++;
    //右边的拿进来一个并更新状态
    temp = s.charAt(end);
    ch[temp - 'a']--;
    if (ch[temp - 'a'] >= 0)
        rest--;
    end++;
    // 状态合法就存到结果集合
    if (rest == 0)
        res.add(start);
}

return res;

}

phoenixflyingsky commented 2 years ago

public List findAnagrams(String s, String p) {

List<Integer> res = new LinkedList<>();
if (s == null || p == null || s.length() < p.length())
    return res;

int[] ch = new int[26];

for (char c : p.toCharArray())
    ch[c - 'a']++;

int start = 0, end = 0, rest = p.length();
for (; end < p.length(); end++) {
    char temp = s.charAt(end);
    ch[temp - 'a']--;
    if (ch[temp - 'a'] >= 0)
        rest--;
}

if (rest == 0)
    res.add(0);

while (end < s.length()) {

    char temp = s.charAt(start);
    if (ch[temp - 'a'] >= 0)
        rest++;
    ch[temp - 'a']++;
    start++;

    temp = s.charAt(end);
    ch[temp - 'a']--;
    if (ch[temp - 'a'] >= 0)
        rest--;
    end++;

    if (rest == 0)
        res.add(start);
}

return res;

}

dereklisdr commented 2 years ago

class Solution { public: vector findAnagrams(string s, string t) { unordered_map<char, int> need, window; for (char c : t) need[c]++;

    int left = 0, right = 0;
    int valid = 0;
    vector<int> res; // 记录结果
    while (right < s.size()) {
        char c = s[right];
        right++;

        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c])
                valid++;
        }

        while (right - left >= t.size()) {

            if (valid == need.size())
                res.push_back(left);
            char d = s[left];
            left++;

            if (need.count(d)) {
                if (window[d] == need[d])
                    valid--;
                window[d]--;
            }
        }
    }
    return res;
}

};

aiweng1981 commented 2 years ago

思路

思路描述:总觉得滑动窗口算法不如二分法直观。

代码

#代码
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        target = collections.Counter(p)
        ans = []
        for i in range(len(s)):
            if i >= len(p):
                target[s[i - len(p)]] += 1
                if target[s[i - len(p)]] == 0:
                    del target[s[i - len(p)]]
            target[s[i]] -= 1
            if target[s[i]] == 0:
                del target[s[i]]
            if len(target) == 0:
                ans.append(i - len(p) + 1)
        return ans

复杂度

时间复杂度: O(N)

空间复杂度: O(1)

ILoveQier commented 2 years ago

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

lsunxh commented 2 years ago

class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        res = []
        count = dict()
        for c in p:
            count[c] = 0
        count2 = collections.Counter(p)
        for right in range(len(s)):
            left = right - len(p)
            if left >= 0:
                if s[left] in p:
                    count[s[left]] -= 1
            if s[right] in p:
                count[s[right]] += 1
            if count == count2:
                res.append(left + 1)
            right += 1
        return res

Tlntin commented 2 years ago

题目链接

链接

代码

class Solution {
public:
  std::vector<int> findAnagrams(std::string & s, std::string & p) {
    if (s.size() < p.size()) {
      return {};
    }
    std::unordered_map<char, int> dict1;
    for (char & c : p) {
      dict1[c]++;
    }
    std::vector<int> v1;
    int n = s.size() - p.size() + 1;
    std::unordered_map<char, int> temp_dict;
    for (int j = 0; j < p.size(); ++j) {
        temp_dict[s[j]] ++;
    }
    compare_map(temp_dict, dict1, v1, 0);

    for (int i = 1; i < n; ++i) {
      temp_dict[s[i - 1]] --;
      temp_dict[s[i + p.size() - 1]] ++;
      if(temp_dict[s[i - 1]] == 0) {
        temp_dict.erase(s[i - 1]);
      }
      compare_map(temp_dict, dict1, v1, i);
    }
    return std::move(v1);
  }

  void compare_map(
    std::unordered_map<char, int> & temp_dict,
    std::unordered_map<char, int> & dict1,
    std::vector<int> & v1,
    int index
  ) {

    bool temp_res = false;
    if (temp_dict.size() == dict1.size()) {
      temp_res = true;
      for (const auto & item: dict1) {
        if (temp_dict[item.first] != item.second) {
          temp_res = false;
        }
      }
    }
    if (temp_res) {
      v1.emplace_back(index);
    }
  }
};

复杂度

时间：O(n)
空间：O(p.size()) = O(1)

提交结果

flaming-cl commented 2 years ago

辅助数据结构

target 目标字符的目标出现次数
window 当前窗口中，目标字符的出现次数

滑动窗口思考题

扩窗：什么时候移动 right 来扩大窗口？right遍历到s底部之前，窗口持续扩大
扩窗时，应该更新哪些数据？
- 碰到 target 字符时
  - 当前window中的字符计数++
  - matched++
缩窗：什么时移动 left 来缩小窗口？窗口中字符种数 >= p.size
缩窗时，应该更新哪些数据？
- 碰到 target 字符时
- 当前window中的字符计数--
- matched--
何时更新结果数据？扩窗 or 缩窗时
- 缩窗时 && 窗口字符种类 == p.size 时
  T: O(N) S:O(N)
```
/**
```
- @param {string} s
- @param {string} p
- @return {number[]} */ var findAnagrams = function(s, p) { const target = {}, window = {}; for (ch of p) target[ch] = (target[ch] || 0) + 1; const targetSize = Object.keys(target).length; let r = 0, l = 0, matched = 0; const res = []; while (r < s.length) { const ch = s[r++]; if (target[ch]) { window[ch] = (window[ch] || 0) + 1; if (target[ch] == window[ch]) matched++; } while (r - l >= p.length) { if (matched == targetSize) res.push(l); const ch1 = s[l++]; if (target[ch1] && window[ch1]-- == target[ch1]) matched--; } } return res; };

leungogogo commented 2 years ago

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ret = new ArrayList<>();
        int[] freq = new int[26];
        for (int i = 0; i < p.length(); i++) {
            freq[p.charAt(i) - 'a']++;
        }

        int left = 0, right = 0;
        while (right < s.length()) {
            while (right < s.length() && right < left + p.length()) {
                freq[s.charAt(right) - 'a']--;
                right++;
            }

            if (check(freq)) {
                ret.add(left);
            }

            freq[s.charAt(left) - 'a']++;
            left++;
        }
        return ret;
    }

    private boolean check(int[] freq) {
        for (int i = 0; i < freq.length; i++) {
            if (freq[i] != 0) {
                return false;
            }
        }
        return true;
    }
}

Time: O(p + s)

Space: O(26) = O(1)

Skylarxu214 commented 2 years ago

思路:

套用滑动窗口模版

var findAnagrams = function(s, p) {
    let res = []
    let need = new Map(), window = new Map();
    for (let c of p){
        need.set(c, (need.get(c) || 0)+1);
    }
    let left = 0, right = 0, valid = 0;
    while(right < s.length){
        const c = s[right];
        right ++;
        if(need.has(c)){
            window.set(c, (window.get(c) || 0 )+1);
            if(window.get(c) === need.get(c)){
                valid ++;
            }
        }
        while( right - left >= p.length){
            const d = s[left];
            if(valid === need.size){
                res.push(left)
            }
            left ++;
            if(need.has(d)){
                if(window.get(d) === need.get(d)){
                    valid --;       
                }
                 window.set(d, window.get(d)-1)

            }
        }
    }
    return res
};

复杂度：

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

eden-ye commented 2 years ago

代码

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int m = s.length();
        int n = p.length();
        List<Integer> res = new ArrayList<>();
        if (m < n) return res;
        int[] dic = new int[26];
        for (char c : p.toCharArray()) {
            dic[c - 'a']++;
        }
        int count = 0;
        for (int i = 0; i < 26; i++) {
            if (dic[i] != 0) count++;
        }
        int left = 0, right = 0;
        int b = 0;
        while (right < m) {
            dic[s.charAt(right) - 'a']--;
            if (dic[s.charAt(right) - 'a'] == 0) {
                b++;
            }
            if (right - left + 1 > n) {
                dic[s.charAt(left) - 'a']++;
                if (dic[s.charAt(left) - 'a'] == 1) {
                    b--;
                }
                left++;
            }
            if (b == count) res.add(left);
            right++;
        }
        return res;
    }
}

复杂度

时间复杂度：O(M + N)
空间复杂度：O(1)

Whisht commented 2 years ago

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        from collections import Counter
        res = []
        l = 0
        c0 = Counter(p)
        for r in range(len(s)):
            if s[r] in c0:
                c0[s[r]] -= 1
            # print(f"{c0} {l} {r}")
            if r >= len(p)-1:
                if  self.check(c0.values()):
                    res.append(l)
                if s[l] in c0:
                    c0[s[l]] += 1
                l += 1
        return res

    def check(self,t):
        for i in t:
            if i != 0:
                return False
        return True

taihui commented 2 years ago

from collections import Counter

class Solution: def findAnagrams(self, s: str, p: str) -> List[int]:

first, let's get the mapper of p

    p_mapper = Counter(p)
    p_size = len(p)

    l = 0
    r = 0
    window = {}

    result = []

    while r < len(s):

        cur_ch = s[r]
        r += 1

        if cur_ch not in p_mapper:
            l = r
            window = {}
        else:
            if cur_ch in window:
                window[cur_ch] += 1
            else:
                window[cur_ch] = 1

            if r-l == p_size:
                if window == p_mapper:
                    result.append(l)
                    window[s[l]] -= 1
                    l += 1
                else:
                    window[s[l]] -= 1
                    l += 1
    return result

haoyangxie commented 2 years ago

code

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new LinkedList<>();
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        if (s.length() < p.length()) {
            return res;
        }

        for(int i=0;i<p.length();i++){
            sCount[s.charAt(i)-'a']++;
            pCount[p.charAt(i)-'a']++;
        }

        if (Arrays.equals(sCount, pCount)) {
            res.add(0);
        }

        for (int i = 0; i < s.length() - p.length(); i++) {
            sCount[s.charAt(i) - 'a']--;
            sCount[s.charAt(i + p.length()) - 'a']++;
            if (Arrays.equals(sCount, pCount)) {
                res.add(i + 1);
            }
        }

        return res;
    }
}

complexity

Time: O(n) Space: O(1)

maoting commented 2 years ago

思路：

滑动窗口用2个数组（new Array(26）)记录每个字符出现的次数

代码

var findAnagrams = function(s, p) {
    const sLen = s.length, pLen = p.length;

    if (sLen < pLen) {
        return [];
    }

    const ans = [];
    const sCount = new Array(26).fill(0);
    const pCount = new Array(26).fill(0);
    for (let i = 0; i < pLen; ++i) {
        ++sCount[s[i].charCodeAt() - 'a'.charCodeAt()];
        ++pCount[p[i].charCodeAt() - 'a'.charCodeAt()];
    }

    if (sCount.toString() === pCount.toString()) {
        ans.push(0);
    }

    for (let i = 0; i < sLen - pLen; ++i) {
        --sCount[s[i].charCodeAt() - 'a'.charCodeAt()];
        ++sCount[s[i + pLen].charCodeAt() - 'a'.charCodeAt()];

        if (sCount.toString() === pCount.toString()) {
            ans.push(i + 1);
        }
    }

    return ans;
};

复杂度分析

时间复杂度O(N)
空间复杂度O(Σ)（Σ = 52）

y525 commented 2 years ago

class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: ans = [] l, r = 0, 0 pCounter = Counter(p) sCounter = Counter() while r < len(s): c = s[r] if c in pCounter: sCounter[c] += 1

if the character at right pointer exceeds limit -> move left pointer after the first occurring same character

            while l < r and sCounter[c] > pCounter[c]:
                sCounter[s[l]] -= 1
                l += 1
            if sCounter == pCounter:
                ans.append(l)
            r += 1
        else:
            sCounter.clear()
            r += 1
            l = r

    return ans

richypang commented 2 years ago

代码


class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        s_len, p_len = len(s), len(p)

        if s_len < p_len:
            return []

        ans = []
        s_count = [0] * 26
        p_count = [0] * 26
        for i in range(p_len):
            s_count[ord(s[i]) - 97] += 1
            p_count[ord(p[i]) - 97] += 1

        if s_count == p_count:
            ans.append(0)

        for i in range(s_len - p_len):
            s_count[ord(s[i]) - 97] -= 1
            s_count[ord(s[i + p_len]) - 97] += 1

            if s_count == p_count:
                ans.append(i + 1)

        return ans

zch-bit commented 2 years ago

Day 45

func findAnagrams(s string, p string) []int {
    have, want := [26]int{}, [26]int{}; for i := range p { want[s[i]-'a']++ }
    res := []int{}
    left := 0
    for right := range s {
        have[s[right]-'a']++
        if right >= len(p) { have[s[left]-'a']--; left++ }
        if want == have { res = append(res, left) }
    }
    return res
}

Time: O(n), space O(n)

UCASHurui commented 2 years ago

思路

滑动窗口比较窗口中字符的出现次数。

代码

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(s) < len(p): return []
        count_p = collections.Counter(p)
        count_s = defaultdict(int)
        for i in range(len(p)):
            count_s[s[i]] += 1
        def same():
            for char, val_p in count_p.items():
                if count_s[char] != val_p:
                    return False
            return True
        l, r = 0, len(p) - 1
        ans = []
        while r < len(s):
            if same():
                ans.append(l)
            if r == len(s) - 1: break
            r += 1
            count_s[s[r]] += 1
            count_s[s[l]] -= 1
            l += 1
        return ans

复杂度分析

时间复杂度：O(NM), N是s长度， M是p中不同字符的种类数
空间复杂度：O(M)

uyplayer commented 2 years ago


//
//  findAnagrams
//  @Description:
//  @param s
//  @param p
//  @return []int
//
func findAnagrams(s string, p string) []int {
    ns := len(s)
    mp := len(p)
    left := 0
    right := 0
    hashP := make(map[byte]int)
    window := make(map[byte]int)
    ans := make([]int, 0)
    for _, ch := range p {
        hashP[byte(ch)]++
    }
    valid := 0
    for right < ns {
        ch := s[right]
        right++
        if _, ok := hashP[byte(ch)]; ok {
            window[byte(ch)]++
            if window[byte(ch)] == hashP[byte(ch)] {
                valid++
            }
        }

        for right-left >= mp {
            if valid == len(hashP) {
                ans = append(ans, left)
            }
            elemLeft := s[left]
            left++
            if _, ok:=hashP[byte(elemLeft)];ok {
                if window[byte(elemLeft] == hashP[byte(elemLeft)]{
                    valid--
                }
                window[byte(elemLeft]--
            }
        }

    }
    return ans
}

//
//  findAnagrams
//  @Description:
//  @param s
//  @param p
//  @return []int
//
func findAnagrams1(s string, p string) []int {
    ns := len(s)
    mp := len(p)
    ans := make([]int,0)
    if mp > ns {
        return ans
    }
    var hashS  [26]int
    var hashP  [26]int
    for i,ch := range p {
        hashS[s[i]-'a'] ++
        hashP[ch - 'a'] ++
    }
    if hashS== hashP {
        ans = append(ans, 0)
    }
    for i, ch := range s[:ns-mp] {
        hashS[ch-'a']--
        hashS[s[i+mp]-'a']++
        if hashS == hashP {
            ans = append(ans,i+1)
        }

    }

    return ans
}

func findAnagrams2(s string, p string) []int {
    ns := len(s)
    mp := len(p)
    ans := make([]int,0)
    if mp > ns {
        return ans
    }
    var hashS  [26]int
    var hashP  [26]int
    for _,ch := range p {
        hashP[ch - 'a'] ++
    }
    left := 0
    right := 0

    for right  < ns {
        ch := s[right]
        hashS[ch-'a']++
        if  (right - left +1)  == mp{
            if hashS == hashP {
                ans = append(ans,left)
            }
            left ++
            hashS[s[left-1]-'a']--
        }
        right++
    }
    return ans
}

time ：o(N) 字符串s的长度
space ：o(1 )

LiquanLuo commented 2 years ago

/***
Solution
1. construct target_map: array[26]  O(p)
2. current_map: array[26]
3. L = R = 0
4. iterate through the string O(n)
    ++current[c]
    (1) target[c] = 0, L = R + 1, --cur[c]      // does not appear 
    (2) current[c] > target[c], ++L until current[c] <= target[c]  // too much
5. if R-L == p.size(), result++

Time: O(p) + O(n)
Space: O(p)
***/

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        unordered_map<char, int> target;
        for (auto c : p) {
            target[c] += 1;
        }

        unordered_map<char, int> cur;
        vector<int> results;
        int L = 0;
        for (int R = 0; R < s.size(); ++R) {
            // cout << "L" << L << " R " << R << endl;
            char c = s[R];
            ++cur[c];
            if (!target.count(c)) {
                L = R + 1;
                cur.clear();
                continue;
            }

            while (cur[c] > target[c]) {
                --cur[s[L]];
                ++L;
            }

            if ((R - L) == (p.size() - 1)) {
                results.push_back(L);
            }
        }

        return results;

    }
};

LuckyRyan-web commented 2 years ago

/**
 * leetcode: https://leetcode.cn/problems/find-all-anagrams-in-a-string/
 * Tags: 滑动窗口
 * @author liuyuan
 * @date 2022-08-28 14:53
 * @since 1.0.0
 */

interface KeyMap {
    [key: string]: number
}

function findAnagrams(s: string, p: string): number[] {
    // const sLen = s.length
    // const pLen = p.length

    // // 先判断长度比较
    // if (sLen < pLen) {
    //     return []
    // }

    const need: KeyMap = {}
    const win: KeyMap = {}

    for (let i of p) {
        need[i] = (need[i] || 0) + 1
    }

    let left = 0
    let right = 0

    // 与滑动窗口大小一样的字符串种类，如果出现次数跟 p 一样就 push
    let val = 0
    const result: number[] = []

    // 右指针进行滑动
    while (right < s.length) {
        let c = s[right]
        right++

        if (need[c]) {
            win[c] = (win[c] || 0) + 1

            if (win[c] === need[c]) {
                val++
            }
        }

        // 这里需要判断不出窗口的情况，限制每次滑动窗口的大小都是等于 p.length
        while (right - left >= p.length) {
            if (val === Object.keys(need).length) {
                result.push(left)
            }

            let d = s[left]
            left++

            if (need[d]) {
                if (win[d] === need[d]) {
                    val--
                }
                win[d]--
            }
        }
    }

    return result
}

joeymoso commented 2 years ago

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        ans = []
        if len(p) > len(s):
            return ans
        p_counter = Counter(p)

        n = len(p)

        s_counter = Counter(s[:n])
        if s_counter == p_counter:
                ans.append(0)
        l, r = 1, n

        while r < len(s):
            s_counter[s[l - 1]] -= 1
            if s_counter[s[l - 1]] == 0:
                del s_counter[s[l - 1]] 
            s_counter[s[r]] += 1 
            if s_counter == p_counter:
                ans.append(l)
            l += 1
            r += 1

        return ans

wzasd commented 2 years ago

思路

这里是滑动窗口的解决办法，但是这次比较简单，只需要处理滑动窗口，并对char数组进行排序，在对比一下targetchar即可，但是算法可能效率不高

代码

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ansList = new ArrayList<>();
        int slideLen = p.length();
        var chars = p.toCharArray();
        Arrays.sort(chars);
        for (int i = 0; i < s.length() - slideLen + 1; i++) {
            if (findCharAtKey(chars, slideLen, s.substring(i, i + slideLen))) {
                ansList.add(i);
            }
        }
        return ansList;
    }

    private boolean findCharAtKey(char[] chars, int len, String targetString){
        var targetChars = targetString.toCharArray();
        Arrays.sort(targetChars);
        return Arrays.equals(chars, targetChars);
    }

xy147 commented 2 years ago

思路

滑动窗口

js代码

var findAnagrams = function(s, p) {
    const sLen = s.length, pLen = p.length;

    if (sLen < pLen) {
        return [];
    }

    const ans = [];
    const sCount = new Array(26).fill(0);
    const pCount = new Array(26).fill(0);
    for (let i = 0; i < pLen; ++i) {
        ++sCount[s[i].charCodeAt() - 'a'.charCodeAt()];
        ++pCount[p[i].charCodeAt() - 'a'.charCodeAt()];
    }

    if (sCount.toString() === pCount.toString()) {
        ans.push(0);
    }

    for (let i = 0; i < sLen - pLen; ++i) {
        --sCount[s[i].charCodeAt() - 'a'.charCodeAt()];
        ++sCount[s[i + pLen].charCodeAt() - 'a'.charCodeAt()];

        if (sCount.toString() === pCount.toString()) {
            ans.push(i + 1);
        }
    }

    return ans;
};

wyz999 commented 2 years ago

思路

滑动窗口

代码

func findAnagrams(s string, p string) []int {
    sLen,pLen := len(s),len(p)
    var ans []int
    if sLen<pLen {
        return ans
    }
    var sCount,pCount [26]int
    for i,v := range p{
        sCount[s[i]-'a']++
        pCount[v-'a']++
    }
    if sCount==pCount{
        ans = append(ans,0)
    }
    for k,w := range s[:sLen-pLen]{
        sCount[w-'a']--
        sCount[s[k+pLen]-'a']++
        if sCount==pCount{
            ans = append(ans,k+1)
        }
    }
    return ans
}

时空复杂度

时间复杂度：O(len(p)+(len(s)-len(p))*Σ),Σ为所有可能的字符数
空间复杂度：O(Σ),用于存储字符串 p和滑动窗口中每种字母的数量

naomiwufzz commented 2 years ago

思路：双指针+哈希

用一个定长的窗口扫一遍s，把s和p重合的词放进hash，窗口扫的hash和目标hash进行对比，一样则加到结果中

代码

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(p) > len(s):
            return []
        target_hash_map = dict()
        for w in p:
            target_hash_map[w] = target_hash_map.get(w, 0) + 1
        hash_map = dict()
        l = 0
        res = []
        for r, w in enumerate(s):
            if w in target_hash_map:
                    hash_map[w] = hash_map.get(w, 0) + 1                
            if r >= len(p):
                if s[l] in target_hash_map:
                    hash_map[s[l]] = hash_map.get(s[l]) - 1
                l += 1
            if hash_map == target_hash_map:
                res.append(l)
        return res

复杂度分析

时间复杂度：O(n)
空间复杂度：O(1) 哈希表中的单词最多26个，不是O(n)，是O(1)

testplm commented 2 years ago

import collections
class Solution:
    def findAnagrams(self, s, p):
        myDictP=collections.Counter(p)
        myDictS=collections.Counter(s[:len(p)])
        output=[]
        i=0
        j=len(p)

        while j<=len(s):
            if myDictS==myDictP:
                output.append(i)

            myDictS[s[i]]-=1
            if myDictS[s[i]]<=0:
                myDictS.pop(s[i])

            if j<len(s):    
                 myDictS[s[j]]+=1
            j+=1
            i+=1

        return output

复杂度分析

时间复杂度：O(n),n为s的长度
空间复杂度：O(1)

ashleyyma6 commented 2 years ago

Idea

count & save character frequency of string p in an array
left, right pointer, update the character frequency between left and right, compare to string p
Code

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int[] countP = new int[26];
        char[] pArr = p.toCharArray();
        for(char c:pArr){
            countP[c-'a']++;
        }
        int[] countS = new int[26];
        char[] sArr = s.toCharArray();
        int left = 0;
        int right = 0;
        List<Integer> result = new ArrayList<>();
        while(right<s.length()){
            countS[sArr[right]-'a']++;
            if(right-left+1>p.length()){
                countS[sArr[left]-'a']--;
                left++;
            }
            if(right-left+1==p.length() && isEqual(countP, countS)){
               result.add(left);
            }
            right++;
        }
        return result;
    }
    public boolean isEqual(int[] p, int[] s){
         for(int i =0;i<26;i++){
            if(p[i]!=s[i]){
                return false;
            }
         }
        return true;
    }
}

Complexity Analysis

Time Complexity:O(s+p) // s = s.length. p = p.length
Space Complexity:O(s+p)

luckyoneday commented 2 years ago

代码 js

var findAnagrams = function (s, p) {
    const wordSet = new Set([...p]);
    const wordMap = [...p].reduce((prev, cur) => {
        return { ...prev, [cur]: (prev[cur] || 0) + 1 }
    }, {});
    const res = [];
    const wordObj = {}, pLen = p.length;
    let valid = 0;

    for (let i = 0; i < s.length; i++) {
        const right = s[i];

        wordObj[right] = (wordObj[right] || 0) + 1;
        if (wordObj[right] === wordMap[right]) {
            valid++
        }

        if (i >= pLen) {
            const left = s[i - pLen]

            if (wordObj[left] === wordMap[left]) {
                valid--
            }
            wordObj[left] = (wordObj[left] - 1) || 0;

        }
        if (valid === wordSet.size) {
            res.push(i - pLen + 1)
        }

    }
    return res;
}

tian-pengfei commented 2 years ago

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int s_n =s.size();
        int p_n = p.size();
        vector<int> ans;
        if(s_n<p_n)return ans;
        unordered_map<int,int> map;
        int p1 =0;
        int p2 =0;
        for(auto c:p){
            map[c]++;
        }
        while (p2<p_n){
            int c_p2 = s[p2++];
            map[c_p2]--;
            if(!map[c_p2])map.erase(c_p2);
        }
        if(map.empty())ans.push_back(p1);

        while (p2<s_n){
            int c_p2 = s[p2++];
            map[c_p2]--;
            if(!map[c_p2])map.erase(c_p2);

            int c_p1 = s[p1++];
            map[c_p1]++;
            if(!map[c_p1])map.erase(c_p1);
            if(map.empty())ans.push_back(p1);
        }
        return ans;
    }
};

adamw-u commented 2 years ago

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        s_len, p_len = len(s), len(p)

        if s_len < p_len:
            return []

        ans = []
        s_count = [0] * 26
        p_count = [0] * 26
        for i in range(p_len):
            s_count[ord(s[i]) - 97] += 1
            p_count[ord(p[i]) - 97] += 1

        if s_count == p_count:
            ans.append(0)

        for i in range(s_len - p_len):
            s_count[ord(s[i]) - 97] -= 1
            s_count[ord(s[i + p_len]) - 97] += 1

            if s_count == p_count:
                ans.append(i + 1)

        return ans

PerfQi commented 2 years ago

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int[] cnt = new int[128];
        for (char c : p.toCharArray()) cnt[c]++;
        int lo = 0, hi = 0;
        List<Integer> res = new ArrayList<>();
        while (hi < s.length()) {
            if (cnt[s.charAt(hi)] > 0) {
                cnt[s.charAt(hi++)]--;
                if (hi - lo == p.length()) res.add(lo);
            } else {
                cnt[s.charAt(lo++)]++;
            }
        }
        return res;
    }
}

youzhaing commented 2 years ago

题目：438. 找到字符串中所有字母异位词

思路

滑动窗口+计数

python代码

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(p) > len(s):
            return []
        s_cnt, p_cnt = [0]*26, [0]*26
        res = []
        # index=0
        for i in range(len(p)):
            p_cnt[ord(p[i]) - ord('a')] += 1
            s_cnt[ord(s[i]) - ord('a')] += 1
        if p_cnt == s_cnt: res.append(0)

        for i in range(len(p), len(s)): #position in s
            s_cnt[ord(s[i]) - ord('a')] += 1
            s_cnt[ord(s[i - len(p)]) - ord('a')] -= 1
            if s_cnt == p_cnt:
                res.append(i - len(p) + 1)

        return res

复杂度

时间复杂度：O(m + (n-m)*c), m=len(p), n=len(s), c=26
空间复杂度：O(c)

zzzkaiNS commented 2 years ago

思路

双指针 + 哈希表

代码

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        unordered_map<char, int> hp;
        unordered_map<char, int> hs;
        int n = p.size();
        vector<int> res;
        for (char c : p) hp[c] ++;
        for (int i = 0, j = 0; i < s.size(); i ++) {
            hs[s[i]] ++;
            while (hs[s[i]] > hp[s[i]]) hs[s[j ++]] --;
            if (n == i - j + 1) res.push_back(j);
        }
        return res;
    }
};

Kaneyang commented 2 years ago

思路

滑动窗口

异位词: 1. 字符串长度相同 2. 每个字母出现的次数相同

代码

from typing import List
from collections import Counter

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        l, r = 0, len(p)
        p_hash = Counter(p)
        cur_hash = Counter(s[l:r])
        ans = []
        while r<=len(s):
            if cur_hash == p_hash:
                ans.append(l)

            cur_hash[s[l]] -= 1
            if cur_hash[s[l]] <= 0:
                cur_hash.pop(s[l])
            if r<len(s):
                cur_hash[s[r]] += 1
            l +=1
            r +=1
        return ans

复杂度分析

时间复杂度: O(∣s∣)

空间复杂度: O(1)

DuanYaQi commented 2 years ago

Day 45. 438. 找到字符串中所有字母异位词

思路

滑动窗口，用数组存字符的个数，匹配是否跟 p 的数组相等

如果用 map ，键值是 0 的话还要erase，较复杂
注意循环的时候 i 从 0 开始，表示走过第 i 个位置，答案是 i+1，注意循环终止条件

vector<int> findAnagrams(string s, string p) {
    int n1 = s.size(), n2 = p.size();
    if (n1 < n2) return {};

    vector<int> ump(26);
    vector<int> now(26);

    for (char c : p) {
        ump[c - 'a']++;
    }

    vector<int> res;

    for (int i = 0; i < n2; ++i) {
        now[s[i] - 'a']++;
    }

    if (now == ump) res.push_back(0);

    for (int i = 0; i < n1 - n2; ++i) {
        now[s[i] - 'a']--;
        now[s[i+n2] - 'a']++;
        if (now == ump) res.push_back(i + 1);
    }
    return res;
}

时间复杂度: O(NΣ), N 是 nums 的长度

空间复杂度: O(Σ)，Σ 是字母表长度

xxiaomm commented 2 years ago

// O(n), O(1)
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int[] cnt = new int[128];
        for (int i = 0; i < p.length(); i++)
            cnt[p.charAt(i)]++;     // 所需字母数量, 其他都是0

        int need = p.length();
        List<Integer> res = new LinkedList<>();
        for (int l = 0, r = 0; r < s.length(); r++) {
            char c = s.charAt(r);
            cnt[c]--;
            // 当字母数量多了 / 包含不合法的字母
            while (l <= r && cnt[c] < 0)
                cnt[s.charAt(l++)]++;
            if (r - l+ 1 == p.length()) res.add(l);
        }
        return res;
    }
}

AtaraxyAdong commented 2 years ago

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        // 使用固定窗口, 小写字母组成，我们就可以使用两个数组
        int len1 = s.length();
        int len2 = p.length();
        if(len1 < len2) return new ArrayList<>();

        // 开始滑动窗口
        int left = 0, right = len2;
        int[] a = new int[26];
        int[] b = new int[26];
        ArrayList<Integer> c = new ArrayList<>();
        for(int i = 0; i < len2; i++){
            a[s.charAt(i) - 'a']++;
            b[p.charAt(i) - 'a']++;
        }

        if(Arrays.equals(a, b)) c.add(0);

        while(right < len1){
            a[s.charAt(right) - 'a']++;
            a[s.charAt(left) - 'a']--;
            if(Arrays.equals(a, b)) c.add(left + 1);
            right++;
            left++;
        }
        return c;
    }
}

ghost commented 2 years ago

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

Thinking:

滑动窗口

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length(), pLen = p.length();

        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }

        List<Integer> ans = new ArrayList<Integer>();
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        for (int i = 0; i < pLen; ++i) {
            ++sCount[s.charAt(i) - 'a'];
            ++pCount[p.charAt(i) - 'a'];
        }

        if (Arrays.equals(sCount, pCount)) {
            ans.add(0);
        }

        for (int i = 0; i < sLen - pLen; ++i) {
            --sCount[s.charAt(i) - 'a'];
            ++sCount[s.charAt(i + pLen) - 'a'];

            if (Arrays.equals(sCount, pCount)) {
                ans.add(i + 1);
            }
        }

        return ans;
    }
}

Time Complexity O(m+(n−m)×Σ) Space Complexity O(Σ)

ceramickitten commented 2 years ago

思路

滑动窗口，每次只需要关心进出窗口的字符。

代码


from collections import Counter
from typing import List

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        s_len, p_len = len(s), len(p)
        if s_len < p_len:
            return []
        char_diff_counter = Counter(p)
        win_counter = Counter(s[:p_len])
        diff_char_count = 0
        for ch in char_diff_counter:
            char_diff_counter[ch] -= win_counter[ch]
            diff_char_count += (char_diff_counter[ch] != 0)
        result = []
        for i in range(s_len - p_len + 1):
            if diff_char_count == 0:
                result.append(i)
            if s[i] in char_diff_counter:
                char_diff_counter[s[i]] += 1
                if char_diff_counter[s[i]] == 0:
                    diff_char_count -= 1
                elif char_diff_counter[s[i]] == 1:
                    diff_char_count += 1
            if i + p_len < s_len and s[i + p_len] in char_diff_counter:
                char_diff_counter[s[i + p_len]] -= 1
                if char_diff_counter[s[i + p_len]] == 0:
                    diff_char_count -= 1
                elif char_diff_counter[s[i + p_len]] == -1:
                    diff_char_count += 1
        return result

复杂度分析

Time: O(s.length) 遍历s每个字符，每次只处理进出的字符
Space: O(p.length) 哈希表统计p每个字符的频率

leetcode-pp / 91alg-8-daily-check

【Day 45 】2022-08-28 - 438. 找到字符串中所有字母异位词 #60

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

入选理由

题目地址

前置知识

题目描述

Python solution

Complexity

Idea

Code

Idea

思路

代码

复杂度

题目链接

代码

复杂度

提交结果

辅助数据结构

滑动窗口思考题

T: O(N) S:O(N)

思路:

复杂度：

代码

first, let's get the mapper of p

code

complexity

思路：

代码

复杂度分析

if the character at right pointer exceeds limit -> move left pointer after the first occurring same character

代码

Day 45

思路

代码

复杂度分析

思路

代码

思路

js代码

思路

代码

时空复杂度

思路：双指针+哈希

代码

复杂度分析

Idea

Code

代码 js

题目：438. 找到字符串中所有字母异位词

思路

python代码

复杂度

思路

代码

思路

滑动窗口

异位词: 1. 字符串长度相同 2. 每个字母出现的次数相同

代码

复杂度分析

时间复杂度: O(∣s∣)

空间复杂度: O(1)

Day 45. 438. 找到字符串中所有字母异位词

思路

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

思路

代码

复杂度分析