Frequency Counter - validAnagram(빈도수 세기 - 애너그램)

문제

Given two strings, write a function to determine if the second string is an anagram of the first. An anagram is a word, phrase, or name formed by rearranging the letters of another, such as cinema, formed from iceman.
두 개의 문자열이 주어지고, 두번째 문자열이 첫번째 문자열의 애너그램인지 결정하는 함수를 만들어라. 
애너그램은 iceman에서 만들어진 cinema처럼 문자을 재배열한 단어 혹은 구문입니다.

Examples:
validAnagram('', '') // true
validAnagram('aaz', 'zza') // false
validAnagram('anagram', 'nagaram') // true
validAnagram("rat","car") // false) // false
validAnagram('awesome', 'awesom') // falsevalidAnagram('amanaplanacanalpanama', 'acanalmanplanpamana') // false
validAnagram('qwerty', 'qeywrt') // true
validAnagram('texttwisttime', 'timetwisttext') // true

Note: You may assume the string contains only lowercase alphabets.
Time Complexity - O(n)

 

나의 코드

• Frequency Counter Pattern에 따라 for 루프를 사용한다.
• 시간복잡도는 O(n) 이어야 하므로 for 문이 이중이면 안된다.
• arr1과 arr2의 letter와 letter의 갯수를 담은 object를 만들어 각 key와 value값을 비교한다.

function validAnagram(arr1, arr2){
  // add whatever parameters you deem necessary - good luck!
  // 1. length check
  if(arr1.length === 0 && arr2.length === 0){
      return true;
  }
  if(arr1.length !== arr2.length){
      return false;
  }
  
  let arr1countObj = {};
  let arr2countObj = {};
  
  // 2. make object from array1
  for(const value of arr1){
      arr1countObj[value] = (arr1countObj[value] || 0) +1;
  }
  // 3. make object from array2
  for(const value of arr2){
      arr2countObj[value] = (arr2countObj[value] || 0) +1;
  }
  // 4. return check value of the same key from arrary1 and array2
  for(const key in arr1countObj){
      if(arr1countObj[key] !== arr2countObj[key]){
          return false;
   }
   return true;
  }
  
  console.log(validAnagram("rat","car")); // false

 

강의에서의 정답

• 나의 코드는 문제에서의 조건, 결과가 맞았다.
• 그러나 나는 첫번째 문자열과 두번째 문자열이 object를 각각 만들어서 비교했는데, 강의에서는 하나의 object로 충분히 비교가 가능한 방향이었다. object도 메모리를 차지하는 부분이니, object를 다중으로 정의해야하는 경우 꼭 그래야하는 것인지 다시 한 번도 고민해봐야겠다는 생각이 들었다.

function validAnagram(first, second){
	// 문자열 길이를 체크하기
	if(first.length !== second.length){
    	return false;
    }
   
    const lookup = {};
    
    for(let i = 0; i<first.length; i++){
    	let letter = first[i];
        //if letter exists, increment, otherwise set to 1
        lookup[letter] ? lookup[letter] += 1 : lookup[letter] = 1;
    }
    
    // validAnagram("apple","apply")이면 lookup = { a:1, p:2, l:1, e:1}이 되겠다.
    
    for(let i = 0; i<second.length; i++){
    	let letter = second[i];
        
        if(!lookup[letter]){
        	// y의 경우
        	return false;
        }else{
        	// a, p, l이 해당하는경우
        	lookup[letter] -= 1;
        }
    }
    
    return true;
}

console.log(validAnagram("apple","apply")) // false

 

강의 : https://www.udemy.com/share/106X8E3@Lt-njJ7uYB8WJ1Fa57QDkC-Jt8Jccl8YSfNg-Ss97_zbUJPT4bPNz4Cynqye826R/