https://leetcode.com/problems/ransom-note/description/?envType=study-plan-v2&envId=top-interview-150
1. 문제 분석
문제분석
--------------------
- ransomNote, magazine 두 문자열이 주어진다.
- magazine으로 ransomNote가 구성될 수 있으면 true, 그렇지 않으면 false를 반환하라.
- magazine에 있는 각 문자는 ransomNote에 한번씩만 사용될 수 있다.
제한조건
--------------------
- 1 <= ransomNote.length, magazine.length <= 10^5
- ransomNote, magazine은 영어 소문자로 구성된다.
2. 접근 방법
접근방법
--------------------
magazine 의 hashMap을 만들어 갯수를 카운팅한다.
ransomNote를 순회하여 hashMap에서 없으면 false를 반환한다.
3. 코드
var canConstruct = function(ransomNote, magazine) {
const hash = {};
for (let letter of magazine) {
hash[letter] = (hash[letter] || 0) + 1
}
for (let letter of ransomNote) {
if (hash[letter]) {
hash[letter]--;
} else {
return false;
}
}
return true;
};
4. 복잡도 분석
- 시간복잡도: O(m+n), m == magazine.length, n == ransomNote.length
- 공간복잡도: O(1)
hashMap을 사용하여 magazine의 문자열의 갯수보다 ransomNote 문자열이 적거나 존재 하지 않는다면 false를 반환하고,
해당 반복문이 종료될 때 까지 false를 반환하지 않았다면 true를 반환한다.
'Leetcode' 카테고리의 다른 글
[Leetcode] 290. Word Pattern - JS (0) | 2024.10.17 |
---|---|
[Leetcode] 205. Isomorphic Strings - JS (0) | 2024.10.16 |
[Leetcode] 289. Game of Life - JS (0) | 2024.10.14 |
[Leetcode] 73. Set Matrix Zeroes - JS (0) | 2024.10.12 |
[Leetcode] 48. Rotate Image - JS (3) | 2024.10.11 |