Leetcode - Find All Anagrams in a String

wanderer-s·2022년 2월 2일
0

Algorithm

목록 보기
17/19
post-thumbnail

Problem

Find All Anagrams in a String
Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input: s = "abab", p = "ab"
Output: [0,1,2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

Constraints:

  • 1 <= s.length, p.length <= 3 * 10⁴
  • s and p consist of lowercase English letters.

Solution

JavaScript

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
    const pObj = {}
    
    for(const key of p) {
        if(!(key in pObj)) {
            pObj[key] = 0
        }
        pObj[key]++
    }
    
    let left = 0
    let right = 0
    let checkCount = p.length
    const result = []
    while(right < s.length) {
        if(pObj[s[right]] > 0) checkCount--
        
        pObj[s[right]]--
        right++
        
        if(checkCount === 0) result.push(left)
        
        if(right - left === p.length) {
            if(pObj[s[left]] >= 0) checkCount++
            pObj[s[left]]++
            left++
        }
    }
    return result
};

Feedback은 언제나 환영입니다🤗

profile
You only get one life. It's actually your duty to live it as fully as possible.

0개의 댓글