자바스크립트 - 빈도수 세기 패턴 anagram

문제

빈도수 세기- validAnagram

두 개의 문자열이 주어졌을 때, 

두 번째 문자열이 첫 번째 문자열의 애너그램인지 확인하는 함수를 작성합니다. 

애너그램은 다른 글자의 글자를 재배열하여 형성된 단어, 구 또는 이름입니다. (예시: cinema -> iceman)

 

그냥 풀이 1

function validAnagram(str1, str2){
  if (str1.length !== str2.length) {
      return false;
  }
  
  str1 = str1.split('').sort((function compare(a, b) {
    if (a > b) return -1;
    if (a < b) return 1;
    return 0;
  }))
  
  str2 = str2.split('').sort((function compare(a, b) {
    if (a > b) return -1;
    if (a < b) return 1;
    return 0;
  }));
  
  for (let i = 0; i < str1.length; i++) {
      const char1 = str1[i];
      const char2 = str2[i];
      
      if (char1 !== char2) {
          return false;
      }
  }
  return true;
}

 

빈도수 세기 패턴과는 상관 없이 sort 함수를 이용함

sort의 함수의 시간 복잡성은 O(n log n)

 

빈도수 세기 패턴을 이용한 풀이 2

function validAnagram(first, second) {
    if (first.length !== second.length) {
        return false;
    }

    const counter = {}

    for (char of first) {
        counter[char] ? counter[char]++ : counter[char] = 1;
    }

    for (char of second) {
        if (!counter[char]) {
            return false;
        } else {
            counter[char] -= 1;
        }
    }
    return true;
}

console.log(validAnagram('', '')) // true
console.log(validAnagram('aaz', 'zza')) // false
console.log(validAnagram('anagram', 'nagaram')) // true
console.log(validAnagram("rat","car")) // false) // false
console.log(validAnagram('awesome', 'awesom')) // false
console.log(validAnagram('amanaplanacanalpanama', 'acanalmanplanpamana')) // false
console.log(validAnagram('qwerty', 'qeywrt')) // true
console.log(validAnagram('texttwisttime', 'timetwisttext')) // true

 

위의 빈도수 세기 패턴을 이용하면 

시간 복잡성은 O(n)

 

빈도수 세기 패턴은 객체를 만들어서 해당 빈도를 저장 후,

중복된 반복문 없이 하나의 반복문 만으로 빈도수를 체크 하는 방법입니다.

 

위 코드는 counter 에 첫번째 파라미터의 문자의 개수를 key, value로 저장하고,

두번째 파라미터의 문자와 비교하는 방법입니다.