Leetcode 242. Valid Anagram

242. Valid Anagram

 

 

Easy

 

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

 

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

Input: s = "rat", t = "car"
Output: false

 

Constraints:

• 1 <= s.length, t.length <= 5 * 104
• s and t consist of lowercase English letters.

 

---

이번문제는 릿코드 242번 문제 Valid Anagram 입니다.

Anagram 은 두 단어들 또는 문장들이 있을 때, 한 단어 / 문장의 배열 순서만 바꿨을 때 다른 나머지 단어 / 문장과 일치하는 것을 뜻합니다.

예를 들어보면, Example 1 의 anagram 에서 나오는 단어의 빈도수를 적어보겠습니다.

 

단어	빈도수
a	3
n	1
g	1
r	1
m	1

 

Example 1의 다른 단어 nagaram 에서 나오는 단어의 빈도수 역시 위의 표와 일치합니다.

따라서, 한 단어가 다른 단어를 재배치 한 것과 일치하므로 이 두 단어는 서로 Anagram 이라고 할 수 있겠습니다.

한글로 예를 들어보면, 릿코드의 경우 [릿드코, 코드릿, 코릿드, 드릿코, 드코릿] 등이 Anagram 입니다.

---

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
    if (s.length != t.length) return false;
    
    const hashMap = {};
    for (let i=0; i<s.length; i++) {
        if (!hashMap[s[i]]) {
            hashMap[s[i]] = 0;
        }
        hashMap[s[i]]++;
    }

    for (let j=0; j<t.length; j++) {
        if (!hashMap[t[j]]) {
            return false;
        }
        hashMap[t[j]]--;
    }
    return true;
};

이번 문제의 경우

Map 을 사용해서 풀어보았습니다.

 

일단 인자로 받은 두 단어의 길이가 일치하지 않을 경우, 복잡한 연산 없이 바로 false 를 리턴할 수 있습니다.

두 단어의 길이가 같지 않으면 Anagram 이 아니겠죠?

그리고 난 직후 map 오브젝트를 생성하고, 처음 인자로 받은 's' string으로 for 루프를 돕니다.

key가 null 일 경우(initialize 되지 않은 경우)에는 해쉬맵에 0을 대입합니다.

모든 s의 문자들에 대해 증감연산자를 통해 1씩 값을 증가시켜줍니다.

 

첫번째 for 루프가 돈 직후의 hashMap 모습입니다.

첫 값을 0으로 해주고 모든 값에 대해 1을 증가 시켜줌으로 첫번째 인자 's'에 대해 hashMap 을 완성했습니다.

---

이제 두번째 't' 스트링으로 for loop 를 돌려봅니다.

이때는 hashMap[t[j]] 의 값이 null 이거나 0일 경우, 두 단어가 서로 anagram 이 아니므로 바로 false를 리턴할 수 있습니다.

hashMap[t[j]] 의 값이 null 이거나 0일 경우 둘다

if (!hashMap[t[j]])

으로 확인이 가능합니다.

1. hashMap[t[j]]의 값이 null 일 경우 - 's'스트링에 없는 알파벳이 't' 스트링에 나온 경우 입니다. 당연히 Anagram이 될 수 없습니다.
2. hashMap[t[j]]의 값이 0일 경우 - 's'스트링의 해당 알파벳 빈도수 보다 't' 스트링에 해당 알파벳 빈도수가 많은 경우 입니다.

---

모든 루프를 돌게 되면 인자로 받은 두 단어의 길이가 같으므로 해쉬맵을 다시 검사 해 볼 필요 없이, 두 단어는 Anagram 이 됩니다.

따라서 true를 마지막에 별도의 검사 없이 리턴해줍니다.

---

Map이용 성능

 

Time Complexity 의 경우 O(n)이 됩니다. 루프를 두 번 돌지만 각각 돌았기 때문에 s, t 스트링의 길이만큼 돌기 때문입니다.

Space Complexity 의 경우 O(n)이 됩니다. 최악의 경우 모든 알파벳이 1번 등장할 수 있기 때문에 hashMap 에 모든 단어의 빈도수가 1로 등록이 되기 때문입니다.

---

Valid Anagram 의 경우 Junior Software Developer 포지션 인터뷰 질문에서 나오는 빈도수가 꽤 높은 편입니다.

연습 많이 하셔서 꼭 원하시는 결과 얻으시길 바랍니다!

 

※ 앞으로 모든 문제를 JavaScript 로 올릴 예정입니다.

 

다른 문제 풀이도 깃헙에서 확인 할 수 있습니다.