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
}