438. Find All Anagrams in a String

문제링크: https://leetcode.com/problems/find-all-anagrams-in-a-string/

s의 substring중에 p의 anagram인 경우를 찾아 시작 index들을 구하는 문제다.

Solution

1. Sliding window with char code array

Anagram인지 확인하기 위해선 구간에 있는 배열이 각 문자를 몇개씩 포함하고 있는지 확인하여 알 수 있다. 한번의 확인을 위해선 문자열의 길이만큼 O(n)의 시간이 소요되지만 이후에 다음 문자열을 확인할 때는 추가된 문자와 삭제된 문자의 수를 계산한다면 O(1)의 시간복잡도로 추가적인 확인을 할 수 있다. 따라서 구간을 이동시켜가는 sliding window를 구현해 총 O(n)의 탐색으로 subarray가 anagram인 곳을 찾을 수 있다.

Algorithm

• p에 들어있는 문자의 개수를 count하기 위해 req배열에 charCode를 통해 count를 맵핑한다. (필요한 개수를 음수로 지정)
• Subarray의 길이는 항상 p.length와 같으므로 처음 0 ~ p.length의 구간의 문자열 개수를 더한다.
• 앞에서부터 i ~ i+p.length의 구간이 anagram인지 확인하기 위해 isAnagram을 통해 모든 req배열이 0인지 확인하여 result에 추가한다.
• 확인이 끝난 후 맨 앞에 원소를 제거하고 뒤의 원소를 추가해 다음 반복을 실행한다.
• 문자열 끝까지 반복이 끝난 후 결과를 반환한다.

var findAnagrams = function(s, p) {
  // anagram인지 확인
  // sliding window 로 count 추가 제거
  // anagram 여부를 확인하기 위해 배열 사용
  const req = new Array(26).fill(0);
  for (let i = 0; i < p.length; i++) {
    req[p.charCodeAt(i) - 97]--;
  }
  const isAnagram = () => {
    for (let count of req) {
      if (count !== 0) return false;
    }
    return true;
  }
  
  for (let i = 0; i < p.length; i++) {
    req[s.charCodeAt(i) -97]++;
  }
  
  const result = [];
  for (let i = 0; i <= s.length - p.length; i++) {
    if (isAnagram()) result.push(i);
    req[s.charCodeAt(i) - 97]--;
    req[s.charCodeAt(i + p.length) - 97]++;
  }
  return result;
};

총 O(n)의 시간복잡도와 O(1)의 공간 복잡도를 사용한다.

2. Sliding window with hash map

문자열이 단순하다면 ex)'aaaa' a~z까지의 모든 req배열을 탐색할 필요가 없다고 생각했다. 따라서 필요한 부분만 hashmap으로 만들어 구현해 보면 유리할 때가 있다고 생각해 구현해보았다.

Algorithm

• 필요한 문자열의 개수를 저장할 needed 를 Map으로 만든다.
• p에들어있는 문자에 대해 count를 저장한다.
• 1번과 같은 sliding window로 문자의 count를 추가 및 제거하고 needed의 values가 모두 0인지 판단해 result에 추가한다.

var findAnagrams = function(s, p) {
  // anagram인지 확인
  // sliding window
  // hash map
  const needed = new Map();
  for (let letter of p) {
    needed.set(letter, (needed.get(letter) ?? 0) + 1);
  }
    
  const isAnagram = () => {
    for (let count of needed.values()) {
      if (count !== 0) return false;
    }
    return true;
  }
  
  for (let i = 0; i < p.length; i++) {
    const curLetter = s[i];
    if (needed.has(curLetter)) needed.set(curLetter, needed.get(curLetter) - 1);
  }
  
  const result = [];
    if (isAnagram()) result.push(0);
  for (let i = 1; i <= s.length - p.length; i++) {
    const prev = s[i-1], next = s[i + p.length - 1];
    if (needed.has(prev)) needed.set(prev, needed.get(prev) + 1);
    if (needed.has(next)) needed.set(next, needed.get(next) - 1);
    if (isAnagram()) result.push(i);
  }
  return result;
};

Hash map의 형태는 단순한 몇몇 특이 케이스에 강하지만 어쨌든 문제에 총 26개의 문자만 존재하기 때문에 O(1)의 시간복잡도를 가지는 것은 동일했다. 따라서 Map을 만들고 추가적인 get set 연산을 위한 오버헤드와 단순 배열 계산을 비교했을 때 큰 차이가 없어서 비슷한 결과가 나왔다고 생각한다.