[Medium] 438. Find All Anagrams in a String

1. 문제

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.

 

두 개의 문자열과 p가 주어지면 p의 아나그램의 모든 시작 지수 배열을 s 단위로 반환합니다. 답변은 어떤 순서로든 반환할 수 있습니다.
아나그램(Anagram)은 다른 단어나 구문의 글자를 재정렬하여 만들어진 단어나 구를 말한다.

 

2. 예시

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".

 

3. 제약 조건

Constraints:

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

 

4. 해결 과정

처음에 내 손으로 코드를 풀어보려고 했는데 계속 time limit에 걸려서 해결이 되지 못했다 😢

그래서 discuss를 참고하여 문제를 해결하였다.

 

p의 문자를 neededCahrs 객체에 저장한다.

 

left와 right는 0부터 시작하여 while문을 순회한다.

right가 먼저 순회하며 한 글자씩 확인하다. 

left와 right의 간격이 p.length와 일치하면 count === 0 이나 !== 0인 경우로 나뉜다.

count ===0 이면 아나그램이므로 시작 인덱스인 left를 push한다.

count !==0 이면 right 인덱스가 순회하며 감소시켰던 값들을 다시 증가시켜 원래 상태로 돌려놓는다.

 

p의 모든 문자에 대해 확인을 하기 위해 count 변수를 초기화한다.

neededCahrs[s[ringt]]의 값이 0보다 크면 count를 1만큼 감소시킨다.

neededCahrs[s[ringt]]의 값을 확인했기 때문에 neededCahrs[s[ringt]]의 값도 1만큼 감소시킨다.

right의 인덱스 값을 1만큼 증가시킨다.

 

count의 값이 0이 된다면 p를 전부 확인한 것이기 때문에 left의 값을 push한다.

right에서 left의 값을 뺀 값이 p.length과 같다면 left 인덱스를 기준으로 아나그램인지 확인한다.

 

 

5. 해결 코드

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function (s, p) {
    const output = [];
    const neededChars = {};

    for (let char of p) {
        if (char in neededChars) {
            neededChars[char]++
        } else neededChars[char] = 1
    }

    let left = 0;
    let right = 0; 
    let count = p.length     

    while (right < s.length) {
        if (neededChars[s[right]] > 0) count--;
        neededChars[s[right]]--;
        right++;        
        if (count === 0) output.push(left);         
        if (right - left == p.length) {            
            if (neededChars[s[left]] >= 0) count++;        
            neededChars[s[left]]++;
            left++;
        }
    }
    return output;
};javascript