383. Ransom Note

---

Description

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.

Each letter in magazine can only be used once in ransomNote.

 

Example 1:

Input: ransomNote = "a", magazine = "b"
Output: false
Example 2:

Input: ransomNote = "aa", magazine = "ab"
Output: false
Example 3:

Input: ransomNote = "aa", magazine = "aab"
Output: true
 

Constraints:

1 <= ransomNote.length, magazine.length <= 105
ransomNote and magazine consist of lowercase English letters.

---

Code

func canConstruct(ransomNote string, magazine string) bool {
	noteMap := make(map[rune]int)
	for _, r := range ransomNote {
		noteMap[r]++
	}
	for _, m := range magazine {
		noteMap[m]--

		if noteMap[m] < 0 {
			return false
		}
	}
	for _, v := range noteMap {
		if v > 0 {
			return false
		}
	}
	return true
}

 

코드는 주어진 ransomNote 문자열이 magazine 문자열을 사용하여 구성될 수 있는지 확인하는 효율적인 방법을 구현합니다. 먼저 ransomNote 문자열과 magazine 문자열에서 각 문자의 빈도수를 세는데 사용할 맵을 만듭니다.

그런 다음, magazine 문자열을 순회하면서 각 문자의 빈도수를 빼고, 만약 해당 문자의 빈도수가 음수가 되면 ransomNote를 만들 수 없다는 것을 의미하므로 즉시 false를 반환합니다.

마지막으로, 만약 noteMap에 양수인 값이 남아있다면, ransomNote를 만들기 위해 필요한 문자가 magazine에 부족하다는 것을 의미하므로 false를 반환합니다.

이 알고리즘은 각 문자열을 한 번씩만 순회하므로 시간 복잡도는 O(n + m)이고, 여기서 n은 ransomNote의 길이이고 m은 magazine의 길이입니다. 공간 복잡도는 고유 문자의 개수에 따라 달라집니다.