[Leetcode] 242. Valid Anagram - JS

https://leetcode.com/problems/valid-anagram/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
- s, t 문자열이 주어질 때, t가 s의 아나그램인지 판단하라.
- 아나그램은 모든 문자를 1번씩만 사용하여 재배열한 단어를 말한다.

제한조건
--------------------
- 1 <= s.length, t.length <= 5 * 10^4
- s, t는 영어 소문자로 구성된다.

 

2. 접근 방법

접근방법
--------------------
s의 해쉬맵을 만들어 사용된 문자를 센다.
t를 순회하면서 해쉬맵에 존재하면 갯수를 제거해주고 없으면 false를 반환한다.

 

 

3. 코드

var isAnagram = function(s, t) {
    const hash = {};
    
    if (t.length !== s.length) return false;

    for (let ch of s) {
        hash[ch] = (hash[ch] || 0) + 1;
    }

    for (let ch of t) {
        if (hash[ch]) {
            hash[ch]--;
        } else {
            return false
        }
    }
    return true;
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n)

- 공간복잡도: O(n)

 

해쉬맵을 사용하여 문자의 갯수를 세준 뒤 t의 문자의 갯수를 빼주면서 아나그램인지 비교하였다.

이 외의 방법으로 sort로 두 문자열을 정렬한 뒤 동일한지 비교하는 방법도 있다.