5/18 목 [LeetCode #242] 유효한 아나그램 TIL

[LeetCode] 242. Valid Anagram

문제:

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.

Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?

나의 풀이:

// Double for loop로 풀이
// TIme: O(N)
// Space: O(N)
function mapSolution(s, t) {
	if (s.length !== t.length) {
		return false;
	}
	const map = new Map();
    for (let letter of s) { // O(N)
        map.set(letter, (map.get(letter) ?? 0) + 1);
    }
    for (let letter of t) { // O(N)
        map.set(letter, (map.get(letter) ?? 0) - 1);
        if (map.get(letter) < 0) {
            return false;
        }
    }

    return true;
}

// Time: O(N) 
// Space: O(N) (one Hash Map)
function objectSolution(s, t) {
    if (s.length !== t.length) {
        return false;
    }

    const countCharacter = {};
    for (const character of s) { // O(N)
        countCharacter[character] = (countCharacter[character] ?? 0) + 1;
    }

    for (const character of t) { // O(N)
        countCharacter[character] = (countCharacter[character] ?? 0) - 1;
        // when t has a character that doesn't exist in s, or when the current character count surpasses that of s: 
        if (countCharacter[character] < 0) {
            return false;            
        }
    }

    return true;
}

다른 풀이:

// 두 문자열을 먼저 정렬하고 같은 인덱스별로 비교하는 방법. 정렬에 필요한 공간을 계산에 넣지 않는다면 O(1)의 공간 복잡도로 해결할 수 있게 된다. 

// Time: 2 * O(NlogN) + O(N)
// Space: O(1) (if not consider sorting memory)
function sortSolution(s, t) {
    if (s.length !== t.length) {
        return false;
    }

    s = s.split('').sort(); // O(NlogN)
    t = t.split('').sort(); // O(NlogN)
    for (let index in s) { // O(N)
        if (s[index] !== t[index]) {
            return false;
        }
    }

    return true;
}

마지막 해법의 공간 복잡도 부분에서 의문이 생겨서 비교해보려고 한다. 우선 간단한 방법은 다음과 같다:

// How to let know memory usage for current process:
arr = [1, 2, 3, 4, 5, 6, 9, 7, 8, 9, 10];
arr.reverse();
u = process.memoryUsage().heapUsed / 1024 / 1024;
console.log(`The script uses approximately ${Math.round(u * 100) / 100} MB`);
// => The script uses approximately 13.95 MB

// Look through all memory usage: 
arr = [1, 2, 3, 4, 5, 6, 9, 7, 8, 9, 10];
arr.reverse();
u = process.memoryUsage();
for (let key in u) {
  console.log(`${key} ${Math.round(u[key] / 1024 / 1024 * 100) / 100} MB`);
}
/* => rss 41.69 MB
    heapTotal 15.97 MB
    heapUsed 14.1 MB
    external 0.99 MB
    arrayBuffers 0.73 MB
*/