Zayden

leetcode - Find All Anagrams in a String

July 28, 2023

문제 설명

두 문자열 s와 p가 주어졌을 때, s에 있는 p의 애너그램의 모든 시작 인덱스의 배열을 반환합니다. 어떤 순서로든 답을 반환할 수 있습니다.

애너그램은 다른 단어 또는 구의 글자를 재배열하여 형성된 단어 또는 구문으로, 일반적으로 원래 글자를 모두 정확히 한 번 사용합니다.

  • 예시 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".
  • 예시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".

제약 조건:

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

문제 접근

시작 인덱스, 끝 인덱스를 이용하여 슬라이딩 기법을 이용합니다.

  1. 문자열 p에 대하여 해당 문자열이 나오는 횟수를 info 객체에 저장합니다.
  2. 문자열 s에서 start, end 변수를 index로 활용합니다.
  3. 해당 맞는 문자가 나오면 count 수를 감소 시킵니다.
  4. 해당 count 수가 0 이되는 시점에 start 를 result 배열에 추가한다.
  5. start ~ end 사이에 거리가 p의 길이와 같다면 start 에 1을 더한다 그리고 info 객체에 해당 start에 해당 문자의 횟수 값인 value를 1을 추가한다.
  6. 위 과정을 문자열의 s의 길이만큼 순회한다.
function solution(s, p) {
  const info = {};

  for (const char of p) {
    if (!info.hasOwnProperty(char)) {
      info[char] = 1;
    } else {
      info[char]++;
    }
  }

  let start = 0;
  let end = 0;
  let count = p.length;
  const result = [];

  while (end < s.length) {
    const char = s[end];

    if (info[char] > 0) {
      count--;
    }

    if (info.hasOwnProperty(char)) {
      info[char]--;
    }
    
    end++;

    if (count === 0) {
      result.push(start);
    }

    if (end - start === p.length) {
      if (info[s[start]] >= 0) {
        count++;
      }

      if (info.hasOwnProperty(s[start])) {
        info[s[start]]++;
      }

      start++;
    }
  }

  return result;
};