In the hash method, some scenarios are tailor-made for arrays.

# 383. Ransom Note

LeetCode Problem Link (opens new window)

Given two strings ransomNote and magazine, determine if ransomNote can be constructed from the characters in magazine. Return true if it is possible, otherwise return false.

(Note: Each character in magazine can only be used once in ransomNote.)

Note:

You may assume that both strings contain only lowercase letters.

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

# Approach

This problem is quite similar to 0242.Valid Anagram (opens new window). The problem 0242 checks if string a and string b can form each other, while in this problem, we need to determine if string a can be formed by string b, without considering if b can form a.

The problem demands checking if the first string ransomNote can be constructed from the characters in the second string magazine. Note these two aspects:

"To avoid exposing the handwriting of the ransom note, search for each needed letter in the magazine to express the intended meaning" – this indicates characters from the magazine cannot be reused.
"You may assume that both strings only contain lowercase letters." This implies only lowercase letters are involved, which is crucial.

# Brute Force Method

The initial approach is essentially brute-forcing with two nested loops to search repeatedly. Here’s the code:

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        for (int i = 0; i < magazine.length(); i++) {
            for (int j = 0; j < ransomNote.length(); j++) {
                if (magazine[i] == ransomNote[j]) {
                    ransomNote.erase(ransomNote.begin() + j);
                    break;
                }
            }
        }
        return ransomNote.length() == 0;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14

Time Complexity: O(n^2)
Space Complexity: O(1)

The time complexity here is relatively high, and there's the time-consuming erase operation involved. However, the code can pass this problem.

# Hash Method

Since the problem states only lowercase letters are involved, we can opt for a hash strategy that trades space for time, using an array of length 26 to record the occurrences of characters in magazine.

Then, validate against ransomNote to check if this array contains all the letters needed for ransomNote.

Using an array in hash methods is an application worth noting.

Some might think of opting for a map instead; however, using a map incurs more space overhead compared to an array because a map maintains either a red-black tree or uses a hash function, and is time-consuming. The difference becomes apparent with large data volumes. An array is simpler, more direct, and efficient!

Here’s the code:

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int record[26] = {0};

        if (ransomNote.size() > magazine.size()) {
            return false;
        }
        for (int i = 0; i < magazine.length(); i++) {
            record[magazine[i] - 'a']++;
        }
        for (int j = 0; j < ransomNote.length(); j++) {
            record[ransomNote[j] - 'a']--;
            if (record[ransomNote[j] - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Time Complexity: O(m+n), where m denotes the length of ransomNote and n denotes the length of magazine.
Space Complexity: O(1)

# Versions in Other Languages

# Java:

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote.length() > magazine.length()) {
            return false;
        }
        int[] record = new int[26];
        
        for (char c : magazine.toCharArray()) {
            record[c - 'a'] += 1;
        }
        
        for (char c : ransomNote.toCharArray()) {
            record[c - 'a'] -= 1;
        }
        
        for (int i : record) {
            if (i < 0) {
                return false;
            }
        }
        
        return true;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# Python:

(Version 1) Using Array

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        ransom_count = [0] * 26
        magazine_count = [0] * 26
        for c in ransomNote:
            ransom_count[ord(c) - ord('a')] += 1
        for c in magazine:
            magazine_count[ord(c) - ord('a')] += 1
        return all(ransom_count[i] <= magazine_count[i] for i in range(26))

1
2
3
4
5
6
7
8
9

(Version 2) Using defaultdict

from collections import defaultdict

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        hashmap = defaultdict(int)
        for x in magazine:
            hashmap[x] += 1

        for x in ransomNote:
            value = hashmap.get(x)
            if not value:
                return False
            else:
                hashmap[x] -= 1

        return True

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

(Version 3) Using Dictionary

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        counts = {}
        for c in magazine:
            counts[c] = counts.get(c, 0) + 1
        for c in ransomNote:
            if c not in counts or counts[c] == 0:
                return False
            counts[c] -= 1
        return True

1
2
3
4
5
6
7
8
9
10

(Version 4) Using Counter

from collections import Counter

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        return not Counter(ransomNote) - Counter(magazine)

1
2
3
4
5

(Version 5) Using Count

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        return all(ransomNote.count(c) <= magazine.count(c) for c in set(ransomNote))

1
2
3

(Version 6) Using Count (Simple and Intuitive)

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        for char in ransomNote:
            if char in magazine and ransomNote.count(char) <= magazine.count(char):
                continue
            else:
                return False
        return True

1
2
3
4
5
6
7
8

# Go:

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

1
2
3
4
5
6
7
8
9
10
11
12
13

# JavaScript:

/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
var canConstruct = function(ransomNote, magazine) {
    const strArr = new Array(26).fill(0),
        base = "a".charCodeAt();
    for(const s of magazine) {
        strArr[s.charCodeAt() - base]++;
    }
    for(const s of ransomNote) {
        const index = s.charCodeAt() - base;
        if(!strArr[index]) return false;
        strArr[index]--;
    }
    return true;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# TypeScript:

function canConstruct(ransomNote: string, magazine: string): boolean {
    let helperArr: number[] = new Array(26).fill(0);
    let base: number = 'a'.charCodeAt(0);
    let index: number;
    for (let i = 0, length = magazine.length; i < length; i++) {
        helperArr[magazine[i].charCodeAt(0) - base]++;
    }
    for (let i = 0, length = ransomNote.length; i < length; i++) {
        index = ransomNote[i].charCodeAt(0) - base;
        helperArr[index]--;
        if (helperArr[index] < 0) {
            return false;
        }
    }
    return true;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# PHP:

class Solution {
    /**
     * @param String $ransomNote
     * @param String $magazine
     * @return Boolean
     */
    function canConstruct($ransomNote, $magazine) {
        if (count($ransomNote) > count($magazine)) {
            return false;
        }
        $map = [];
        for ($i = 0; $i < strlen($magazine); $i++) {
            $map[$magazine[$i]] = ($map[$magazine[$i]] ?? 0) + 1;
        }
        for ($i = 0; $i < strlen($ransomNote); $i++) {
            if (!isset($map[$ransomNote[$i]]) || --$map[$ransomNote[$i]] < 0) {
                return false;
            }
        }
        return true;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# Swift:

func canConstruct(_ ransomNote: String, _ magazine: String) -> Bool {
    var record = Array(repeating: 0, count: 26);
    let aUnicodeScalarValue = "a".unicodeScalars.first!.value
    for unicodeScalar in magazine.unicodeScalars {
        let idx: Int = Int(unicodeScalar.value - aUnicodeScalarValue)
        record[idx] += 1
    }
    for unicodeScalar in ransomNote.unicodeScalars {
        let idx: Int = Int(unicodeScalar.value - aUnicodeScalarValue)
        record[idx] -= 1
        if record[idx] < 0 {
            return false
        }
    }
    return true
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# Rust:

impl Solution {
    pub fn can_construct(ransom_note: String, magazine: String) -> bool {
        let baseChar = 'a';
        let mut record = vec![0; 26];
        
        for byte in magazine.bytes() {
            record[byte as usize - baseChar as usize] += 1;
        }
        
        for byte in ransom_note.bytes() {
            record[byte as usize - baseChar as usize] -= 1;
            if record[byte as usize - baseChar as usize] < 0 {
                return false;
            }
        }
        
        return true;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# Scala:

Version 1: Using Array as Hash Table

object Solution {
  def canConstruct(ransomNote: String, magazine: String): Boolean = {
    if (magazine.length < ransomNote.length) {
      return false
    }
    val map: Array[Int] = new Array[Int](26)
    for (i <- magazine.indices) {
      map(magazine(i) - 'a') += 1
    }
    for (i <- ransomNote.indices) {
      if (map(ransomNote(i) - 'a') > 0)
        map(ransomNote(i) - 'a') -= 1
      else return false
    }
    true
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

object Solution {
  import scala.collection.mutable
  def canConstruct(ransomNote: String, magazine: String): Boolean = {
    if (magazine.length < ransomNote.length) {
      return false
    }
    val map = new mutable.HashMap[Char, Int]()
    for (i <- magazine.indices) {
      val tmpChar = magazine(i)
      if (map.contains(tmpChar)) {
        map.put(tmpChar, map.get(tmpChar).get + 1)
      } else {
        map.put(tmpChar, 1)
      }
    }
    for (i <- ransomNote.indices) {
      val tmpChar = ransomNote(i)
      if (map.contains(tmpChar) && map.get(tmpChar).get > 0) {
        map.put(tmpChar, map.get(tmpChar).get - 1)
      } else {
        return false
      }
    }
    true
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# C#:

public bool CanConstruct(string ransomNote, string magazine) {
        if(ransomNote.Length > magazine.Length) return false;
        int[] letters = new int[26]; 
        foreach(char c in magazine){
            letters[c-'a']++;
        }
        foreach(char c in ransomNote){
            letters[c-'a']--;
            if(letters[c-'a'] < 0){
                return false;
            }
        }
        return true;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# C:

bool canConstruct(char* ransomNote, char* magazine) {
    int hashmap[26] = {0};
    while (*magazine != '\0') hashmap[*magazine++ % 26]++;
    while (*ransomNote != '\0') hashmap[*ransomNote++ % 26]--;
    for (int i = 0; i < 26; i++) {
        if (hashmap[i] < 0) return false;
    }
    return true;
}

1
2
3
4
5
6
7
8
9

← 6. 4Sum II 8. 3Sum →