[15일차] Frequence Counter Pattern -2

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.

Examples:
validAnagram('', '') // true
validAnagram('aaz', 'zza') // false
validAnagram('anagram', 'nagaram') // true
validAnagram("rat","car") // false) // false
validAnagram('awesome', 'awesom') // false
validAnagram('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)

어제 글에서의 두번째 예시 풀이를 오늘 해 보도록 하겠다.
간단하게 split()와 sort() 그리고 join()을 이용해서 문제를 풀 수도 있으나, 이번에는 Frequence Counter Pattern을 이용해야한다. 그 말 즉슨 for 루프를 이용해서 솔루션을 제시해야한다. 내가 찾은 해답은 다음과 같다.

function validAnagram(arr1, arr2){
  // add whatever parameters you deem necessary - good luck!
    var checkArr1 = arr1.split("");
    var checkArr2 = arr2.split("");
    
    if(checkArr1.length !== checkArr2.length) {
        return false;
    }
    
    for(let val of checkArr1){
        var index = checkArr2.indexOf(val)
        if(index<=-1){
            return false;
        }else{
            checkArr2.splice(index,1);
        }
        
    }
    
    console.log(arr1)
    return true;

}

안타깝게도 루프 안에서 indexOf()를 사용해 O(n)의 이상적인 복잡성에는 미치지 못했다.
다음은 강의에서 소개한 해답과도 같은 버전이다!

function validAnagram(first, second){
	//문자열 길이를 체크하기 (같은 것만 통과)
	if(first.length !== second.length){
    	return false;
    }
    
    //룩업객체 생성
    /**
    { a : 1, n : 1 etc...}
    **/
    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;
    }
    
    for(let i = 0; i<second.length; i++){
    	let letter = second[i];
        //can't find letter or letter is zero then it's not an anagram
        //0은 falsy이다. 0으로 되었는데 호출한다면 false를 넘겨준다.
        if(!lookup[letter]){
        	return false;
        }else{
        	lookup[letter] -= 1;
        }
    }
    
    return true;
}

위의 해결법은 객체를 생성하여 문자열 글자의 숫자를 세고, 두번째 문자와 비교하면서 숫자를 감소시켰다. 루프를 중첩시키지 않고 객체를 사용하는 것으로 이 문제에서 요구하는 O(n)의 시간 복잡도를 이뤄냈다.

참고

https://www.udemy.com/share/105zfq3@7PUd-DjCUf72mp0eJX_alpLQy0LtihDfJpcI4_fPqHol3epqEAvyS5-T0hsoglH-yg==/