<reponame>ZhengyangXu/Algorithm-Daily-Practice<filename>题源分类/LeetCode/LeetCode日刷/python/438.找到字符串中所有字母异位词.py
#
# @lc app=leetcode.cn id=438 lang=python3
#
# [438] 找到字符串中所有字母异位词
#
# https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/description/
#
# algorithms
# Medium (45.76%)
# Likes:    350
# Dislikes: 0
# Total Accepted:    36.2K
# Total Submissions: 78.7K
# Testcase Example:  '"cbaebabacd"\n"abc"'
#
# 给定一个字符串 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" 的字母异位词。
# 
# 
#

# @lc code=start
class Solution:
    from collections import Counter
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if not s:
            return    
        l,r = 0,0  
        needcnt = len(p)
        need = Counter(p)
        res = []
        while r < len(s):
            if need[s[r]] > 0:
                needcnt -= 1  
            need[s[r]] -= 1 
            r += 1   
            while needcnt == 0:
                if r - l == len(p):
                    res.append(l)
                if need[s[l]] == 0:
                    needcnt += 1  
                need[s[l]] += 1  
                l += 1 
        return res 
    
                
                
# @lc code=end


#
# @lc app=leetcode.cn id=438 lang=python3
#
# [438] 找到字符串中所有字母异位词
#
# https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/description/
#
# algorithms
# Medium (45.76%)
# Likes:    350
# Dislikes: 0
# Total Accepted:    36.2K
# Total Submissions: 78.7K
# Testcase Example:  '"cbaebabacd"\n"abc"'
#
# 给定一个字符串 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" 的字母异位词。
# 
# 
#

# @lc code=start
class Solution:
    from collections import Counter
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if not s:
            return    
        l,r = 0,0  
        needcnt = len(p)
        need = Counter(p)
        res = []
        while r < len(s):
            if need[s[r]] > 0:
                needcnt -= 1  
            need[s[r]] -= 1 
            r += 1   
            while needcnt == 0:
                if r - l == len(p):
                    res.append(l)
                if need[s[l]] == 0:
                    needcnt += 1  
                need[s[l]] += 1  
                l += 1 
        return res 
    
                
                
# @lc code=end
# # @lc app=leetcode.cn id=438 lang=python3 # # [438] 找到字符串中所有字母异位词 # # https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/description/ # # algorithms # Medium (45.76%) # Likes:    350 # Dislikes: 0 # Total Accepted:    36.2K # Total Submissions: 78.7K # Testcase Example:  '"cbaebabacd"\n"abc"' # # 给定一个字符串 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" 的字母异位词。 # # # # @lc code=start # @lc code=end