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" 的字母异位词。

Richard-LYF commented 2 years ago

class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: ans = [] n = len(s) m = len(p) a = [0] 26 aa = [0] 26 if n<m: return ans for i in range(m): a[ord(s[i])-ord('a')] += 1 aa[ord(p[i])-ord('a')] += 1

    if a == aa:
        ans.append(0)

    for i in range(m,n):
        a[ord(s[i])-ord('a')] += 1
        a[ord(s[i - m])-ord('a')] -= 1

        if aa == a:
            ans.append(i - m + 1)

    return ans

on o1

charlestang commented 2 years ago

思路

滑动窗口，维护一个长度为 len(p) 的窗口，扫描 s，记录窗口内每个字母的数量，与 p 中的字母数量比对，相同则为异位词。

时间复杂度 O(len(s))

空间复杂度 O(1) 因为只有小写字母，所以，只需要常数个空间列表就可以记录窗口。

代码

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        pattern = [0] * 26
        window = [0] * 26

        for c in p:
            pattern[ord(c) - ord('a')] += 1
        pn = len(p)
        ans = []

        l = r = 0
        while r < len(s):
            window[ord(s[r]) - ord('a')] += 1
            if r - l + 1 >= pn:
                if window == pattern:
                    ans.append(l)
                window[ord(s[l]) - ord('a')] -= 1
                l += 1
            r += 1
        return ans

yan0327 commented 2 years ago

思路：异位词的概念可以利用数组哈希表表示。只要维护一个滑动窗口，由于是相同则添加入答案数组。所以，一旦不满足搜索条件，则左移。一旦达到窗口长度，则添加值。

func findAnagrams(s string, p string) []int {
    out := []int{}
    if len(s) < len(p){
        return out
    }
    var have,find [26]int
    for i := range p{
        have[p[i]-'a']++
    }
    l := 0
    for r := range s{
        find[s[r]-'a']++ //一遍没有AC的地方在忽视的每次右移的条件！
        for find[s[r]-'a'] > have[s[r]-'a']{
            find[s[l]-'a']--
            l++
        }
        if r-l+1 == len(p){
            out = append(out,l)
        }
    }
    return out
}

时间复杂度：O（N）空间复杂度：O（K） K 为字符串P的长度

laofuWF commented 2 years ago

# sliding window
# keep a count of valid letters in current sliding window
# every time right index moves, check if count == len(p), and add to res
# 3 cases when right index move
# 1. letter in p and hasn't reached total num of p: increment count, update dict
# 2. letter not in p, move left to right + 1, refresh all (count, dict)
# 3. letter in p but went over boundary: move left until first current letter is removed from the left

# time: O(N), length of s
# space: O(M), number of unique letters in p

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        original_letters = collections.defaultdict(int)

        for letter in p:
            original_letters[letter] += 1

        if len(s) < len(p):
            return []

        left = 0
        # number of valid letters in current sliding window
        count = 0
        res = []

        letters = original_letters.copy()
        for right in range(len(s)):
            if s[right] in letters and letters[s[right]] > 0:
                count += 1
                letters[s[right]] -= 1
            elif not s[right] in letters :
                left = right + 1
                count = 0
                letters = original_letters.copy()
            else:
                # too many number of letter s[right] in the window
                # remove letter from left
                while s[left] != s[right]:
                    if s[left] in letters:
                        count -= 1
                        letters[s[left]] += 1
                    left += 1
                left += 1

            if count == len(p):
                res.append(left)

        return res

zhangzz2015 commented 2 years ago

思路

使用固定窗口的slding windows，解决该问题，转化为从s 中找到一个子串，该子串和p相同的字符数。可比较两个字符串具有相同的hash map。时间复杂度为O(n +m)，空间复杂度为 O(1).

关键点

代码

语言支持：C++

C++ Code:


class Solution {
public:
    vector<int> findAnagrams(string s, string p) {

        ///  sliding winwdow.  // only lower case. 
        vector<int> ret;         
        if(s.size()<p.size())
            return ret; 
        vector<int> smap(26,0); 
        vector<int> pmap(26,0); 
        for(int i=0; i< p.size(); i++)
            pmap[p[i]-'a']++; 

        int count =0 ;
        for(int i =0; i< p.size(); i++)
        {
            int index = s[i]-'a'; 
            smap[index]++; 
            if(smap[index]<=pmap[index])
                count++; 
        }
        if(count == p.size())
            ret.push_back(0); 
        for(int i=p.size(); i< s.size(); i++)
        {
            if(s[i]!=s[i-p.size()])
            {
             int index = s[i]-'a'; 
             smap[index]++; 
             if(smap[index]<=pmap[index])
                count++;                 
             index = s[i-p.size()]-'a'; 
             smap[index]--;
             if(smap[index]<pmap[index])
                 count--; 
            }
            if(count == p.size())
                ret.push_back(i-p.size()+1); 
        }
        return ret; 

    }
};

CoreJa commented 2 years ago

思路

哈希+滑动窗口：用dict作为滑动窗口的容器，每次移动窗口时调整dict元素个数，并对比字符串p对应的dict。复杂度$O(abs(s-p)*26)$。
哈希+滑动窗口：上述方法改进，只用一个dict解决问题。复杂度$O(abs(s-p)*26)$。
列表+滑动窗口：上述改进，哈希在对比前需要把计数为0的key丢掉，影响速度，换成定长26的list速度快。复杂度$O(abs(s-p)*26)$
列表+滑动窗口：上述改进，只需要一个list就可以搞定，速度稍慢，复杂度$O(abs(s-p)*26)$

代码

class Solution:
    # 哈希+滑动窗口：用dict作为滑动窗口的容器，每次移动窗口时调整dict元素个数，并对比字符串p对应的哈希。
    # 复杂度$O(abs(s-p)*26)$。
    def findAnagrams1(self, s: str, p: str) -> List[int]:
        n = len(p)
        if n > len(s):
            return []
        cnt = Counter(p)
        cur = Counter(s[:n])
        ans = []
        if cur == cnt:
            ans += [0]
        for i in range(n, len(s)):
            cur[s[i]] += 1
            cur[s[i - n]] -= 1
            if cur[s[i - n]] == 0:
                cur.pop(s[i - n])
            if cur == cnt:
                ans.append(i - n + 1)
        return ans

    # 哈希+滑动窗口：上述方法改进，只用一个dict解决问题。复杂度$O(abs(s-p)*26)$。
    def findAnagrams2(self, s: str, p: str) -> List[int]:
        n = len(p)
        if n > len(s):
            return []
        cnt = Counter(p)
        ans = []
        for i in range(len(s)):
            if i < n:
                cnt[s[i]] -= 1
                if cnt[s[i]] == 0:
                    del cnt[s[i]]
            else:
                cnt[s[i - n]] += 1
                cnt[s[i]] -= 1
                if cnt[s[i - n]] == 0:
                    del cnt[s[i - n]]
                if cnt[s[i]] == 0:
                    del cnt[s[i]]
            if len(cnt) == 0:
                ans += [i - n + 1]
        return ans

    # 列表+滑动窗口：上述改进，哈希在对比前需要把计数为0的key丢掉，影响速度，换成定长26的list速度快。
    # 复杂度$O(abs(s-p)*26)$
    def findAnagrams(self, s: str, p: str) -> List[int]:
        n = len(p)
        if n > len(s):
            return []
        cnt = [0] * 26
        cur = [0] * 26
        for i in range(n):
            cnt[ord(p[i]) - 97] += 1
            cur[ord(s[i]) - 97] += 1
        ans = []
        if cur == cnt:
            ans += [0]
        for i in range(n, len(s)):
            cur[ord(s[i]) - 97] += 1
            cur[ord(s[i - n]) - 97] -= 1
            if cur == cnt:
                ans.append(i - n + 1)
        return ans

    # 列表+滑动窗口：上述改进，只需要一个list就可以搞定，速度稍慢，复杂度$O(abs(s-p)*26)$
    def findAnagrams4(self, s: str, p: str) -> List[int]:
        n = len(p)
        cnt = [0] * 26
        for i in range(n):
            cnt[ord(p[i]) - 97] += 1
        ans = []
        for i in range(len(s)):
            cnt[ord(s[i]) - 97] -= 1
            if i >= n:
                cnt[ord(s[i - n]) - 97] += 1
            if not any(cnt):
                ans.append(i - n + 1)
        return ans

zwx0641 commented 2 years ago

class Solution { public List findAnagrams(String s, String p) { int[] window = new int[26]; int[] charp = new int[26]; List list = new ArrayList<>(); for (char c : p.toCharArray()) { charp[c - 'a']++; }

    int l = 0, r = p.length();
    while (l < s.length() && l < p.length()) {
        window[s.charAt(l) - 'a']++;
        l++;
    }
    l = 0;
    while (l < s.length() - p.length() + 1) {
        if (Arrays.equals(window, charp)) {
            list.add(l);
        }
        if (r < s.length()) {
            window[s.charAt(r++) - 'a']++;
        }
        window[s.charAt(l++) - 'a']--;
    }
    return list;
}

}

zwmanman commented 2 years ago

class Solution(object): def findAnagrams(self, s, p): """ :type s: str :type p: str :rtype: List[int] """ need = collections.Counter(p) window = collections.defaultdict(int)

    l = r = 0
    valid = 0
    res = []

    while r < len(s):
        c = s[r]
        r += 1

        if c in need:
            window[c] += 1
            if window[c] == need[c]:
                valid += 1
        print(l, r) 

        while r - l + 1 > len(p):
            if valid == len(need):
                res.append(l)

            d = s[l]
            l += 1

            if d in need:
                if window[d] == need[d]:
                    valid -= 1

                window[d] -= 1

    return res

wangzehan123 commented 2 years ago

语言支持：Java

Java Code:


public class Solution {
    /**
     * @param s a string
     * @param p a non-empty string
     * @return a list of index
     */
    public List<Integer> findAnagrams(String s, String p) {
        // Write your code here
        List<Integer> ans = new ArrayList <Integer>();
        int[] sum = new int[30];

        int plength = p.length(), slength = s.length();
        for(char c : p.toCharArray()){
            sum[c - 'a'] ++;
        }

        int start = 0, end = 0, matched = 0;
        while(end < slength){
            if(sum[s.charAt(end) - 'a'] >= 1){
                matched ++;
            }
            sum[s.charAt(end) - 'a'] --;
            end ++;
            if(matched == plength) {
                ans.add(start);
            }
            if(end - start == plength){
                if(sum[s.charAt(start) - 'a'] >= 0){
                    matched --;
                }
                sum[s.charAt(start) - 'a'] ++;
                start ++;
            }
        }
        return ans;
    }
}

ZhangNN2018 commented 2 years ago

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

        if len(p) > len(s):
            return []
        p = sorted(p)

        res = []
        Map = {}
        for i in range(len(s)-len(p) + 1):
            s1 = s[i: i+len(p)]
            if s1 in Map: #如果已经在map里，说明是要找的，直接加1，下面不再重复判断
                Map[s1] += 1
                res.append(i)
                continue
            if sorted(s1) == p:
                res.append(i)
                Map[s1] = 1

        return res

xinhaoyi commented 2 years ago

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

给定两个字符串 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" 的异位词。

思路一：压缩数组+滑动窗口

代码

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int[] originString = new int[26];
        int[] subString = new int[26];
        List<Integer> res = new ArrayList<>();
        int lengthOfP = p.length();
        int lengthOfS = s.length();
        if(lengthOfP > lengthOfS){
            return res;
        }
        for(int i = 0; i < lengthOfP; i++){
            originString[p.charAt(i) - 'a'] ++;
        }
        //generate the slide
        for(int i = 0; i < lengthOfP; i++){
            subString[s.charAt(i) - 'a'] ++;
        }
        if(isEqual(originString, subString)){
            res.add(0);
        }
        for(int start = 0, end = lengthOfP; end < lengthOfS;){
            subString[s.charAt(end++) - 'a'] ++;
            subString[s.charAt(start++) - 'a'] --;
            if(isEqual(originString, subString)){
                res.add(start);
            }
        }
        return res;
    }

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

复杂度分析

时间复杂度：$O(n^2)$

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

思路二：改进思路一

你的滑动窗口写的太麻烦了，没必要维护一个和p一样大的滑动窗口，只要这个窗口小于等于p就行，一旦某个元素个数比p中的还要多，就要不断抛弃左端元素，一直到两者相等，甚至有可能全部抛弃光

代码

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int[] originString = new int[26];
        int[] subString = new int[26];
        List<Integer> res = new ArrayList<>();
        int lengthOfP = p.length();
        int lengthOfS = s.length();
        for(int i = 0; i < lengthOfP; i++){
            originString[p.charAt(i) - 'a'] ++;
        }
        int left = 0;
        for(int right = 0; right < lengthOfS; right++){
            //把right对应字母加进来
            int curRightCharacter = s.charAt(right) - 'a';
            subString[curRightCharacter] ++;
            //如果subString中某个字母的个数比originString要大
            //那么说明当前的子窗口要抛弃元素，一直抛弃到当前right指向的元素和originString中的个数相等
            while(subString[curRightCharacter] > originString[curRightCharacter]){
                //看当前最左端字母是多少，把它抛弃掉
                int curLeftCharacter = s.charAt(left) - 'a';
                subString[curLeftCharacter] --;
                left++;
            }
            //出了这个循环后，我们能保证当前子串中存在的字母个数和originalString中的都相等
            //如果两个串长度又相等，那么当前的left就要加进结果集
            if(right - left + 1 == lengthOfP){
                res.add(left);
            }
        }
        return res;
    }
}

复杂度分析

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

空间复杂度：$O(1)$

wdwxw commented 2 years ago

class Solution { public List 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;
}

}

MonkofEast commented 2 years ago

438. Find All Anagrams in a String

Click Me

Algo

EZ write, lapsa time/space: Counter(p), Counter(curr), compare

Opt Solu:

Code_EZ_Write

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        l = 0
        n = len(p)
        target = collections.Counter(p)
        res = []

        while l <= len(s) - n:
            if collections.Counter(s[l:(l + n)]) == target: res.append(l)
            l += 1
        return res

Comp

T: many

S: O(len(p))

Code_Opt_Solu

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        # in code below, manipulate target and only target
        target = collections.Counter(p)
        res = []

        for i in range(len(s)):
            # if i >= len(p), we should "rebalance the credit" of the dropped char in the past window
            # which should not be counted into this window
            if i >= len(p):
                target[s[i - len(p)]] += 1
                # if there is no "credit" after "rebalance"
                # this char should not be counted into the anagram counting
                # we delete it in advance
                if target[s[i - len(p)]] == 0: del target[s[i - len(p)]]

            # 1. every time encounter a char, set counter[char] -= 1
            target[s[i]] -= 1

            # 2. if no "credit" for current char, delete the "account" in target
            if target[s[i]] == 0: del target[s[i]]

            # 3. if all "account" in target has been canceled, that means a match occurs, add this window
            if len(target) == 0: res.append(i - len(p) + 1)

        return res

Comp

T: O(N)

S: O(len(p))

cszys888 commented 2 years ago

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        from collections import defaultdict
        target_dict = defaultdict(int)
        for char in p:
            target_dict[char] -= 1
        lenp = len(p)
        lens = len(s)
        for char in s[:lenp]:
            if char in target_dict:
                target_dict[char] += 1
        result = []
        differ = sum([int(x!=0) for x in list(target_dict.values())])
        if differ == 0:
            result.append(0)

        for idx in range(lenp,lens):
            out_char = s[idx - lenp]
            in_char = s[idx]
            if out_char in target_dict:
                target_dict[out_char] -= 1
                if target_dict[out_char] == 0:
                    differ -= 1
                elif target_dict[out_char] == -1:
                    differ += 1
            if in_char in target_dict:
                target_dict[in_char] += 1
                if target_dict[in_char] == 0:
                    differ -= 1
                elif target_dict[in_char] == 1:
                    differ += 1
            if differ == 0:
                result.append(idx - lenp + 1)
        return result

time complexity: O(M+N+K), M is length of s, N is length of p, K is the number of unique characters in p space complexity: O(K)

moirobinzhang commented 2 years ago

Code:

public class Solution { public IList FindAnagrams(string s, string p) {

    IList<int> res = new List<int>();
    if (s.Length < p.Length)
        return res;

    int[] sDict = new int[26];
    int[] pDict = new int[26];

    foreach(var ch in p)
        pDict[ch - 'a']++;

    int pLen = p.Length;
    for (int i = 0; i < pLen; i++)
        sDict[s[i] - 'a']++;

    int cursoIndex = pLen;
    for (; cursoIndex < s.Length; cursoIndex++)
    {
        if (IsEqual(sDict, pDict ))
            res.Add(cursoIndex - pLen);

        sDict[s[cursoIndex - pLen] - 'a']--;
        sDict[s[cursoIndex] - 'a']++;
    }

    if (IsEqual(sDict, pDict ))
        res.Add(cursoIndex - pLen);

    return res;  
}

public bool IsEqual(int[] sDict, int[] pDict)
{
    for (int i = 0; i < sDict.Length ; i++)
    {
        if (sDict[i] != pDict[i])
            return false;            
    }

    return true;
}

}

GoRedFish commented 2 years ago

代码

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int n = s.length(), m = p.length();
        List<Integer> res = new ArrayList<>();
        if(n < m) return res;
        int[] pCnt = new int[26];
        int[] sCnt = new int[26];
        for(int i = 0; i < m; i++){
            pCnt[p.charAt(i) - 'a']++;
            sCnt[s.charAt(i) - 'a']++;
        }
        if(Arrays.equals(sCnt, pCnt)){
            res.add(0);
        }
        for(int i = m; i < n; i++){
            sCnt[s.charAt(i - m) - 'a']--;
            sCnt[s.charAt(i) - 'a']++;
            if(Arrays.equals(sCnt, pCnt)){
                res.add(i - m + 1);
            }
        }
        return res;
    }
}

Aobasyp commented 2 years ago

思路 Sliding Window

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;

}

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

Tesla-1i commented 2 years ago

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        original_letters = collections.defaultdict(int)

        for letter in p:
            original_letters[letter] += 1

        if len(s) < len(p):
            return []

        left = 0
        # number of valid letters in current sliding window
        count = 0
        res = []

        letters = original_letters.copy()
        for right in range(len(s)):
            if s[right] in letters and letters[s[right]] > 0:
                count += 1
                letters[s[right]] -= 1
            elif not s[right] in letters :
                left = right + 1
                count = 0
                letters = original_letters.copy()
            else:
                # too many number of letter s[right] in the window
                # remove letter from left
                while s[left] != s[right]:
                    if s[left] in letters:
                        count -= 1
                        letters[s[left]] += 1
                    left += 1
                left += 1

            if count == len(p):
                res.append(left)

        return res

ZacheryCao commented 2 years ago

Idea

Sliding window + HashTable. We keep a sliding window with the size of p. Then we use one hashtable to count the letters in current sliding window and another hashset to record all the letters in current sliding window also appears in p and its count is as same as the count in p. When the length of hashset is as same as the count of unique letters in p then we have one anagram.

Code

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        p_count = collections.Counter(p)
        cur_count = {}
        cur_len = set()
        i, j = 0, 0
        ans = []
        while i <= len(s) - len(p):
            ## When the length of current sliding window is one larger than the p
            ## we need to move the left side of the window one step
            if j - i == len(p):
                ## In move the left side of the window, we minus the letter's count by one
                cur_count[s[i]] -= 1
                ## We check whether it is in p 
                if s[i] in p_count:
                    ## whether its count is as same as that in p
                    if p_count[s[i]] == cur_count[s[i]]:
                        ## If so, it means the letter in current sliding window
                        ## has same count in p. we add the letter to the hash set,
                        ## we find a unique letter meeting conditions
                        cur_len.add(s[i])
                        ## If the hash set has same unique letters as p
                        ## we find one anagram we need
                        if len(cur_len) == len(p_count):
                            ans.append(i+1)
                    ## If the count is not as same as in p, we remove this unique letter
                    else:
                        if s[i] in cur_len:
                            cur_len.discard(s[i])
                i += 1
            ## We move the right side of the sliding window one step right till end of s
            if j < len(s):
                ## Count the letter frequency in current sliding window
                cur_count[s[j]] = cur_count.get(s[j], 0) + 1
                ## If the letter appearing in p and has same amount in p
                ## we find on unique letter
                if s[j] in p_count and cur_count[s[j]] == p_count[s[j]]:
                    cur_len.add(s[j])
                ## If the letter appearing in p and doesn't same amount in p
                ## we need to remove this unique letter from set
                else:
                    if s[j] in cur_len:
                        cur_len.discard(s[j])
                ## If the hash set has same unique letters as p
                ## we find one anagram we need
                if len(cur_len) == len(p_count):
                    ans.append(i)
                j += 1
        return ans

Complexity:

Time: O(S +P) Space: O(S+P)

hdyhdy commented 2 years ago

思路：构建两个26个字母的数组，一个用于记录p中字母的情况，另外一个用于记录固定窗口中字母的情况。这里每次滑动窗口的时候，第二个数组只需改变两个地方即可。改变完通过比对两个数组是否相同来确定是否是异位词。

func findAnagrams(s string, p string) []int {
    ans := make([]int,0)
    if len(s) < len(p) {
        return ans
    }

    var que, tem [26]int
    for i := 0 ;  i < len(p); i ++ {
        que[p[i]-'a'] ++
        tem[s[i]-'a'] ++
    }
    if que == tem {
        ans = append(ans,0)
    }

    for i := len(p); i < len(s); i ++ {
        tem[s[i - len(p)] - 'a'] -- 
        tem[s[i] - 'a'] ++
        if tem == que {
            ans = append(ans,i - len(p) + 1)
        }
    }
    return ans 
}

时间复杂度：O(m+(n−m)×Σ) 空间复杂度：O(Σ)

callmeerika commented 2 years ago

思路

利用滑动窗口

代码

var findAnagrams = function (s, p) {
    let pn = p.length;
    let sn = s.length;
    let hash = new Map();
    let res = [];
    for (let i = 0; i < pn; i++) {
      hash.set(p.charAt(i), (hash.get(p.charAt(i)) || 0) + 1);
    }
    let l = 0;
    let r = 0;
    while (r < sn) {
      if (hash.get(s.charAt(r)) !== undefined) {
        hash.set(s.charAt(r), hash.get(s.charAt(r)) - 1);
      }
      while (r - l + 1 > pn) {
        if (hash.get(s.charAt(l)) !== undefined) {
          hash.set(s.charAt(l), hash.get(s.charAt(l)) + 1);
        }
        l++;
      }
      r++;
      let pass = true;
      for (let value of hash.values()) {
        if (value) {
          pass = false;
          break;
        }
      }
      pass && res.push(l);
    }
    return res;
  };

复杂度

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

wenlong201807 commented 2 years ago

代码块


var findAnagrams = function (s, t) {
  // 需要的
  let need = {};
  // 窗口中的字符
  let window = {};
  for (let a of t) {
    // 统计需要的字符
    need[a] = (need[a] || 0) + 1;
  }
  // 左右指针
  let left = 0,
    right = 0;
  let valid = 0;
  let res = [];
  while (right < s.length) {
    // 即将移入窗口的字符
    let c = s[right];
    // 右移窗口
    right++;
    if (need[c]) {
      // 当前字符在需要的字符中，则更新当前窗口统计
      window[c] = (window[c] || 0) + 1;
      if (window[c] == need[c]) {
        // 当前窗口和需要的字符匹配时，验证数量增加1
        valid++;
      }
    }
    while (right - left >= t.length) {
      if (valid == Object.keys(need).length) {
        res.push(left);
      }
      let d = s[left];
      left++;
      if (need[d]) {
        if (window[d] == need[d]) {
          valid--;
        }
        window[d]--;
      }
    }
  }
  return res;
};

时间复杂度和空间复杂度

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

watchpoints commented 2 years ago

思路

稍后补充，在整理

代码

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        int m = s.length();
        int n = p.length();

        if (m < n) {
            // 如果s没p长，直接返回空列表
            return ans;
        }

        int[] sCnt = new int[26];
        int[] pCnt = new int[26];

        for (int i = 0; i < n; i++) {
            sCnt[s.charAt(i) - 'a']++;
            pCnt[p.charAt(i) - 'a']++;
        }

        if (Arrays.equals(sCnt, pCnt)) {
            // 初始窗口就相等
            ans.add(0);
        }

        for (int i = 0; i < m - n; i++) {
            // 窗口右移
            sCnt[s.charAt(i) - 'a']--;
            sCnt[s.charAt(i + n) - 'a']++;

            if (Arrays.equals(sCnt, pCnt)) {
                ans.add(i + 1);
            }
        }

        return ans;
    }
}

Zhang6260 commented 2 years ago

JAVA版本

使用滑动窗口来完成

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int count = p.length();
        int []dp = new int[26];
        for(int i = 0 ; i < p.length() ; i++){
            dp[p.charAt(i)-'a']++;
        }
        int temp = count;
        for(int i = 0; i < s.length(); i++ ){
            //当小于滑动窗口
            if(i<count-1){
                if(dp[s.charAt(i)-'a']>0){
                    temp--;
                }
                dp[s.charAt(i)-'a']--;
                continue;
            }
            //处理滑动窗口的右边
            if(dp[s.charAt(i)-'a']>0){
                temp --;
            }
            dp[s.charAt(i)-'a']--;
            if(temp==0){
                res.add(i-count+1);
            }
            //处理滑动窗口左边
            if(dp[s.charAt(i-count+1)-'a']>=0){
               temp++;
            }
            dp[s.charAt(i-count+1)-'a']++;
        }
        return res;
    }
}

时间复杂度：O(n)

空间复杂度：O(1)

wenjialu commented 2 years ago

thought

sliding win + array as map

code

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
              map_p = {string:0 for string in string.ascii_lowercase }
        map_s = {string:0 for string in string.ascii_lowercase }
        res = []
        # init map_p
        for char in p:
            map_p[char] += 1
        for i in range(len(s)):
            map_s[s[i]] += 1
            if i >= len(p):# when the i > len(p), could mantain the win by del the count of the leftest.
                map_s[s[i - len(p)]] -= 1
            if map_p == map_s:
                res.append(i - len(p) + 1)
        return res

com

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

tongxw commented 2 years ago

思路

定长滑动窗口基础题

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int n = s.length();
        int m = p.length();
        List<Integer> res = new ArrayList<>();
        if ( n < m) {
            return res;
        }

        int[] countS = new int[26];
        int[] countP = new int[26];
        for (int i=0; i<m; i++) {
            countS[s.charAt(i) - 'a']++;
            countP[p.charAt(i) - 'a']++;
        }

        for (int i=m; i<=n; i++) {
            int k = 0;
            for (; k<26; k++) {
                if (countS[k] != countP[k]) {
                    break;
                }
            }
            if (k == 26) {
                res.add(i-m);
            }

            if (i != n) {
                countS[s.charAt(i-m) - 'a']--;
                countS[s.charAt(i) - 'a'] ++;
            }
        }

        return res;
    }
}

TC: O(n) SC: O(n-m)

alongchong 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;
    }
}

yijing-wu commented 2 years ago

// sliding window
// TC = O(N_s + N_p), SC = O(1)
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new LinkedList<Integer>();
        int lenp = p.length();
        int lens = s.length();
        if( lens < lenp ) {
            return ans;
        }
        int[] pCount = new int[26];
        int[] sCount = new int[26];
        // put p into arr pCount
        for(int i = 0; i < lenp; i++) {
            pCount[p.charAt(i) - 'a']++;
        }
        // sliding window on the string s
        for(int i = 0; i < lens; i++) {
            // move the sliding window
            // add one more letter
            sCount[s.charAt(i) - 'a']++;
            if(i >= lenp) {
                // remove one letter
                sCount[s.charAt(i - lenp) - 'a']--;
            }
            if(Arrays.equals(pCount, sCount)) {
                ans.add(i - lenp + 1);
            }
        }
        return ans;
    }
}

linyang4 commented 2 years ago

思路

滑动窗口

对于这种子串排列的问题, 一般用滑动窗口解决, 解决的时候处理好下面几个点就好了

什么时候移动 right 指针(扩大窗口)
移动 right 指针的时候需要更新哪些数据
什么时候移动 left 指针(收缩窗口)
移动 left 指针的时候需要更新哪些数据
怎么判断窗口是子串的排列之一

代码(JavaScript)

var findAnagrams = function(s, p) {
    const ans = []
    if(p.length > s.length) { return ans }
    const targetMap = new Map()
    for(let i = 0; i < p.length; i++) {
        targetMap.set(p[i], (targetMap.get(p[i]) || 0) + 1)
    }
    let left = right = valid = 0
    let window = new Map()
    while(right < s.length) {
        const rightChar = s[right]
        right++
        const targetCount = targetMap.get(rightChar)
        if (targetCount !== undefined) {
            let curCount = (window.get(rightChar) || 0) + 1
            window.set(rightChar, curCount)
            if (curCount === targetCount) { 
                valid++
            } else if (curCount > targetCount) {
                // 需要收缩窗口, 直到curCount = targetCount
                while(curCount > targetCount) {
                    const leftChar = s[left]
                    const leftCount = window.get(leftChar)
                    if (leftCount === targetMap.get(leftChar)) {
                        valid--
                    }
                    if (leftChar === rightChar) {
                        curCount--
                    }
                    window.set(leftChar, leftCount - 1)
                    left++
                }

            }
            if (valid === targetMap.size) { ans.push(left) }
        } else {
            left = right
            valid = 0
            window = new Map()
        }
    }
    return ans
};

复杂度

时间复杂度: O(S)
空间复杂度: O(P)

zol013 commented 2 years ago

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        '''
        ans = []
        i = 0
        cnt1 = Counter(p)
        cnt2 = {}

        for j in range(len(s)):
            cnt2[s[j]] = cnt2.get(s[j], 0) + 1
            if j - i + 1 > len(p):
                cnt2[s[i]] -= 1
                if cnt2[s[i]] == 0:
                    del cnt2[s[i]]
                i += 1

            if cnt1 == cnt2:
                ans.append(i)

        return ans
        '''

        ans = []
        i = 0
        cnt1 = [0] * 26
        cnt2 = [0] * 26
        for char in p:
            cnt1[ord(char) - ord('a')] += 1

        for j in range(len(s)):
            cnt2[ord(s[j]) - ord('a')] += 1

            if j - i + 1 > len(p):
                cnt2[ord(s[i]) - ord('a')] -= 1
                i += 1

            if cnt1 == cnt2:
                ans.append(i)

        return ans

haixiaolu commented 2 years ago

思路

滑动窗口 + 数组

代码

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

        if len_s < len_p:
            return ans 

        p_count = [0] * 26
        s_count = [0] * 26

        for i in range(len_p):
            p_count[ord(p[i]) - ord('a')] += 1

        left = 0
        for right in range(len_s):
            cur_right = ord(s[right]) - ord('a')
            s_count[cur_right] += 1
            while s_count[cur_right] > p_count[cur_right]:
                cur_left = ord(s[left]) - ord('a')
                s_count[cur_left] -= 1
                left += 1
            if right - left + 1 == len_p:
                ans.append(left)
        return ans

复杂度分析

时间复杂度： O(n)
空间复杂度： O(1), 数组是fixed size （26）

LannyX commented 2 years ago

思路

滑起来

代码

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        int[] count = new int[26];
        int n = s.length(), m = p.length();
        for (int i = 0; i < m; i++){
            count[p.charAt(i) - 'a']++;
        }
        int a = 0;
        for(int i = 0; i < 26; i++){
            if(count[i] != 0) a++;
        }
        for(int l = 0, r = 0, b = 0;  r < n; r++){
            if(--count[s.charAt(r) - 'a'] == 0){
                b++;
            }
            if(r - l + 1 > m && ++count[s.charAt(l++) - 'a'] == 1){
                b--;
            }
            if(a == b){
                ans.add(l);
            }
        }
        return ans;
    }

}

复杂度分析

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

ninghuang456 commented 2 years ago

class Solution {
    public List<Integer> findAnagrams(String s, String t) {
        HashMap<Character, Integer> window = new HashMap<>(); 
        HashMap<Character, Integer> need = new HashMap<>();
        List<Integer> res = new ArrayList<>();
        for (char t1 : t.toCharArray()) {
            need.put(t1, need.getOrDefault(t1,0) + 1);
        }
        int left = 0; int right = 0; int valid = 0;
        while (right < s.length()) { // 区间[left, right)是左闭右开的，所以初始情况下窗口没有包含任何元素：
            char s1 = s.charAt(right);
            right ++;
            if (need.containsKey(s1)) {
                window.put(s1,window.getOrDefault(s1,0) + 1);
                if (window.get(s1).equals(need.get(s1))){
                    valid ++;
                }
            }

    // 右指针移动当于在寻找一个「可行解」，然后移动左指针在优化这个「可行解」，最终找到最优解
            while (right - left >= t.length()) {
                 if (valid == need.size()) res.add(left);
                  char s2 = s.charAt(left);
                  left ++;
                  if (need.containsKey(s2)) {s
                   if (window.get(s2).equals(need.get(s2))){ // equals not ==
                      valid --;
                   }
                    window.put(s2,window.get(s2) - 1);
                }
            }
        }
        return res;

    }
}

feifan-bai commented 2 years ago

思路

滑动窗口 + Hashmap

代码

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)

tian-pengfei commented 2 years ago

class Solution {

public:
    //    <字母码值, 个数>
    unordered_map<int,int> m;
    vector<int> findAnagrams(string s, string p) {
        vector<int> re;
        if(s.length()<p.length())return re;
        for(auto const c : p){
            m[c]++;
        }
        int pos1 =0;
        int pos2 = 1;
        while (pos2<=s.length()){
            if(pos2<=p.length()){
                if(!--m[s[pos2-1]]) {
                    m.erase(s[pos2-1]);
                }
                if(m.empty())re.push_back(pos1);
                if(pos2==p.length())pos1++;
                pos2++;
                continue;
            }
            if(!--m[s[pos2-1]]) {
                m.erase(s[pos2-1]);
            }
            if(!++m[s[pos1-1]]) {
                m.erase(s[pos1-1]);
            }
            if(m.empty())re.push_back(pos1);
            pos1++;
            pos2++;
        }
        return re;
    }
};

ZJP1483469269 commented 2 years ago

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        ls = [0] * 26
        if len(s) < len(p):
            return []
        for c in p:
            ls[ord(c) - ord('a')] += 1

        ls1 = [0] * 26

        l , r = 0 , 0
        for _ in range(len(p)):
            ls1[ord(s[r]) - ord('a')] += 1
            r += 1
        ans = []
        if ls == ls1:
            ans.append(0)

        for i in range(0,len(s) - len(p)):
            ls1[ord(s[i]) - ord('a')] -= 1
            ls1[ord(s[i + len(p)]) - ord('a')] += 1
            if ls == ls1:
                ans.append(i+1)
        return ans

biscuit279 commented 2 years ago

滑动窗口记录字母的匹配情况

import collections
class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        #统计p中各个字母出现的次数
        traget = collections.Counter(p)
        ans = []
        for i in range(len(s)):
            if i >= len(p):
                traget[s[i-len(p)]] += 1
                #全部匹配完毕
                if traget[s[i-len(p)]] == 0:
                    del traget[s[i-len(p)]]
            traget[s[i]] -= 1
            if traget[s[i]] ==0:
                del traget[s[i]]
            if len(traget) ==0:
                ans.append(i-len(p)+1)
        return ans

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

zwang2244 commented 2 years ago

思路

Sliding window

代码

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

        int[] counts = new int[26];
        int[] countp = new int[26];

        for(char curr: p.toCharArray()){
            countp[curr - 'a']++;
        }

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

复杂度分析

时间复杂度：O(Ns + Hp)，其中 Ns 为 Length of s，其中 Np 为 Length of p 。
空间复杂度：O(1)

Toms-BigData commented 2 years ago

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

思路

滑动窗口

golang代码

func findAnagrams(s string, p string) (ans []int) {
    hashmapa:= map[uint8]int{}
    for i := 0; i < len(p); i++ {
        hashmapa[p[i]]++
    }
    hashmapb:= map[uint8]int{}
    for k, v:=range hashmapa{
        hashmapb[k] = v
    }
    l:=0
    for j:=0;j<len(s);j++{
        if _,ok:=hashmapa[s[j]];ok{
            hashmapb[s[j]]--
            if hashmapb[s[j]]==0{
                delete(hashmapb, s[j])
            }
            if j-l>=len(p){
                hashmapb[s[l]]++
                if hashmapb[s[l]] == 0{
                    delete(hashmapb, s[l])
                }
                l++
            }
            if len(hashmapb) == 0{
                ans = append(ans, l)
            }
        }else {
            for k := l;k<j;k++{
                hashmapb[s[k]]++
            }
            l = j+1
            if l>=len(s){
                break
            }
        }
    }
    return
}

复杂度

时间:O(n) 空间:O(k)k为s长度

LinnSky commented 2 years ago

思路

滑动窗口

代码

      var findAnagrams = function(s, p) {
          let need  = {}
          let win = {}
          for(let a of p) {
             need[a] = (need[a] || 0) + 1
          }
          let left = 0, right = 0
          let val = 0
          let res = []
          while (right < s.length) {
              let c = s[right]
              right++
              if(need[c]) {
                  win[c] = (win[c] || 0) + 1
                  if(win[c] == need[c]) {
                      val++
                  }
              }
          while(right - left >= p.length) {
              if(val == Object.keys(need).length) {
                  res.push(left)
              }
              let d = s[left]
              left++
              if(need[d]) {
                  if(win[d] == need[d]) {
                      val--
                  }
                  win[d]--
              }
            }
         }
         return res
      };

zhiyuanpeng 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

Yachen-Guo commented 2 years ago

class Solution {
    public List<Integer> 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;
}
}

falconruo commented 2 years ago

思路

用固定宽度的滑动窗口来做

复杂度

时间复杂度: O(n + m)，其中n是字符串s的长度, m是字符串p的长度
空间复杂度: O(1)

代码(C++)

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        if (s.length() < p.length()) return {};

        vector<int> dictP(26, 0);
        vector<int> dictA(26, 0);

        for (auto c : p)
            dictP[c - 'a']++;

        vector<int> res;
        int l = 0;
        for (int r = 0; r < s.length(); ++r) {
            dictA[s[r] - 'a']++;

            if (r >= p.length()) {
                dictA[s[l] - 'a']--;
                ++l;
            }

            if (dictA == dictP)
                res.push_back(l);
        }

        return res;
    }
};

HWFrankFung commented 2 years ago

Codes

var findAnagrams = function(s, t) {
  let need = {};
  let window = {};
  for (let a of t) {
    need[a] = (need[a] || 0) + 1;
  }
  let left = 0,
    right = 0;
  let valid = 0;
  let res = [];
  while (right < s.length) {
    let c = s[right];
    right++;
    if (need[c]) {
      window[c] = (window[c] || 0) + 1;
      if (window[c] == need[c]) {
        valid++;
      }
    }
    while (right - left >= t.length) {
      if (valid == Object.keys(need).length) {
        res.push(left);
      }
      let d = s[left];
      left++;
      if (need[d]) {
        if (window[d] == need[d]) {
          valid--;
        }
        window[d]--;
      }
    }
  }
  return res;
};

jiaqiliu37 commented 2 years ago

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        cnt = [0]*26
        for char in p:
            cnt[ord(char) - ord('a')] += 1

        cur = [0]*26
        ans = []
        i = 0

        for j in range(len(s)):
            cur[ord(s[j]) - ord('a')] += 1
            if j - i + 1 > len(p):
                cur[ord(s[i]) - ord('a')] -= 1
                i += 1
            if j - i + 1 == len(p) and cur == cnt:
                ans.append(i)

        return ans

Time complexity O(n) Space complexity O(1)

xuhzyy commented 2 years ago

思路

滑动窗口

代码

class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        need, window = {}, {}
        for c in p:
            need[c] = need[c] + 1 if c in need else 1
            window[c] = 0
        l, r, valid = 0, 0, 0
        m, n = len(s), len(p)
        res = []
        while(r < m):
            c = s[r]
            if c in window:
                window[c] += 1
                if window[c] == need[c]:
                    valid += 1

            if r - l == n - 1:
                if valid == len(need):
                    res.append(l)
                d = s[l]
                if d in window:
                    if window[d] == need[d]:
                        valid -= 1
                    window[d] -= 1
                l += 1

            r += 1

        return res

复杂度分析

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

wxj783428795 commented 2 years ago

思路

用哈希表或数组记录p中出现的字母及次数
滑动窗口遍历字母s，统计子串中出现的字母及次数，如果相同则计入ans数组中

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function (s, p) {
    let arr = [];
    for (let char of p) {
        let charCode = char.charCodeAt()-97;
        if (arr[charCode] === undefined) {
            arr[charCode] = 1;
        } else {
            arr[charCode] += 1;
        }
    }
    let ans = [];

    for (let i = 0; i < s.length - p.length + 1; i++) {
        let substr = s.slice(i, i + p.length);
        let temp = [];
        for (let char of substr) {
            let charCode = char.charCodeAt()-97;
            if (temp[charCode] === undefined) {
                temp[charCode] = 1;
            } else {
                temp[charCode] += 1;
            }
        }
        let flag = true;
        for (let i = 0; i < arr.length; i++) {
            if (arr[i] !== temp[i]) {
                flag = false;
                break;
            }
        }
        if (flag) {
            ans.push(i);
        }
    }
    return ans;
};

复杂度分析

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

1149004121 commented 2 years ago

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

思路

用哈希表保存p长度窗口的字符差异个数。

代码

var findAnagrams = function(s, p) {
    const lenP = p.length;
    const lenS = s.length;
    if(lenS < lenP) return [];
    let map = new Map();
    let diff = 0;
    let res = [];
    for(let i = 0; i < lenP; i++){
        map.set(p[i], (map.get(p[i]) || 0) - 1);
        map.set(s[i], (map.get(s[i]) || 0) + 1);
    };
    for(let value of map.values()){
        if(value !== 0) diff++;
    }
    if(diff === 0) res.push(0);
    for(let i = 1; i < lenS - lenP + 1; i++){
        let charIn = s[i + lenP - 1];
        let charOut = s[i - 1];

        if(!map.has(charIn) || map.get(charIn) === 0) diff++;
        else if(map.get(charIn) === -1) diff--;
        map.set(charIn, (map.get(charIn) || 0) + 1);

        if(map.get(charOut) === 1) diff--;
        else if(map.get(charOut) === 0) diff++;
        map.set(charOut, map.get(charOut) - 1);

        if(diff === 0) res.push(i);
    };
    return res;
};

复杂度分析

时间复杂度：O(S)。
空间复杂度：O(P)。

ginnydyy commented 2 years ago

Problem

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

Notes

Sliding window.
Original thoughts: use an array to store all the characters of the string p, then sort the array. Then scan the string s, for each substring, store all the characters of the subtring, and sort the array. Compare two arrays to check whether they are anagram.
It costs O(klogk) to sort the substring characters, k is the length of string p. So the total O(nklogk), n is the length of string s. s.length, p.length <= 3 10^4, so O(n*klogk) > 10^8 > 10^7. It causes TLE.
To optimize, can use int[26] to store the characters frequencies of string p. And use another int[26] to store the characters of substrings of string s.
Move the pointer from 0 to p.length() - 1, check the first substring. Then keep moving the pointer to the end of s.length() - 1, updating the int[26], and comparing to the base in[26].
Details: may use Arrays.equals(pCount, sCount) instead of writing method to compare.

Solution

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        if(p.length() > s.length()){
            return new ArrayList<>();
        }

        List<Integer> result = new ArrayList<>();
        int[] base = new int[26];
        for(char c: p.toCharArray()){
            base[c - 'a']++;
        }

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

        if(isValid(base, curr)){
            result.add(0);
        }

        for(int i = p.length(); i < s.length(); i++){
            curr[s.charAt(i) - 'a']++;
            curr[s.charAt(i - p.length()) - 'a']--;
            if(isValid(base, curr)){
                result.add(i - p.length() + 1);
            }
        }

        return result;
    }

    private boolean isValid(int[] base, int[] curr){
        if(base.length != curr.length){
            return false;
        }

        for(int i = 0; i < base.length; i++){
            if(base[i] != curr[i]){
                return false;
            }
        }

        return true;
    }
}

Complexity

Time: O(n + k) n is the s.length(), k is p.length().
Space: O(1) two int[26] arrays.

qiaojunch commented 2 years ago

有漏洞，case： ‘af‘ vs ’de‘。该用hashmap

class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: '''' hint: char is also represented as int in ASCII 'a': 97 'b': 98 'c': 99 ''' k = len(p) p_sum = 0 for i in range(k): p_sum += ord(p[i])

    curr = 0     ## store the sum of int for every p char
    ans = []

    ## do sliding window
    for i in range(len(s)):
        curr += ord(s[i])

        if i >= k-1:  
            if curr == p_sum:       ## find the start index
                ans.append(i-k+1)
            curr -= ord(s[i-k+1])   ## i-k+1 index falls out of window

    return ans

time: o(n) space: o(n)

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

【Day 45 】2022-01-25 - 438. 找到字符串中所有字母异位词 #55

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

入选理由

题目地址

前置知识

题目描述

on o1

思路

代码

思路

关键点

代码

思路

代码

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

思路一：压缩数组+滑动窗口

代码

复杂度分析

思路二：改进思路一

代码

复杂度分析

438. Find All Anagrams in a String

Algo

Code_EZ_Write

Comp

T: many

S: O(len(p))

Code_Opt_Solu

Comp

T: O(N)

S: O(len(p))

Idea

Code

Complexity:

思路

代码

复杂度

代码块

时间复杂度和空间复杂度

思路

代码

JAVA版本

thought

code

com

思路

思路

滑动窗口

代码(JavaScript)

复杂度

思路

代码

复杂度分析

思路

代码

滑动窗口记录字母的匹配情况

思路

代码

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

思路

golang代码

复杂度

思路

代码

Codes

思路

代码

思路

复杂度分析

Problem

Notes

Solution

Complexity

有漏洞，case： ‘af‘ vs ’de‘。 该用hashmap

有漏洞，case： ‘af‘ vs ’de‘。该用hashmap