383. Ransom Note

Problem

Given two stings ransomNote and magazine, return true if ransomNote can be constructed 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 <= 100000
• ransomNote and magazine consist of lowercase English letters.

Problem Summary

To avoid exposing handwriting in the ransom note, search for each needed letter from the magazine and form words to express the meaning.

Given a ransomNote string and a magazine string, determine whether ransomNote can be constructed from the characters in magazine.

If it can be constructed, return true; otherwise, return false.

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

Solution Approach

• Both ransomNote and magazine consist of lowercase letters, so use an array for simple character counting

Code

package leetcode

func canConstruct(ransomNote string, magazine string) bool {
	if len(ransomNote) > len(magazine) {
		return false
	}
	var cnt [26]int
	for _, v := range magazine {
		cnt[v-'a']++
	}
	for _, v := range ransomNote {
		cnt[v-'a']--
		if cnt[v-'a'] < 0 {
			return false
		}
	}
	return true
}