Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/383.html

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.

Algorithm

Hash Map counts the number of characters.

Code

• Java
• C++
• Python
• Go
• TypeScript
• Php
• C#

• import java.util.HashMap;
  import java.util.Map;
  
  public class Ransom_Note {
  
      class Solution {
          public boolean canConstruct(String ransomNote, String magazine) {
  
              if (ransomNote == null || magazine == null || ransomNote.length() > magazine.length()) {
                  return false;
              }
  
              int[] arr = new int[26];
              for (int i = 0; i < magazine.length(); i++) {
                  arr[magazine.toLowerCase().charAt(i) - 'a']++;
              }
              for (int i = 0; i < ransomNote.length(); i++) {
                  if(--arr[ransomNote.toLowerCase().charAt(i)-'a'] < 0) {
                      return false;
                  }
              }
  
              return true;
          }
      }
  
      class Solution_passed {
          public boolean canConstruct(String ransomNote, String magazine) {
              Map<Character, Integer> magM = new HashMap<>();
              for (char c:magazine.toCharArray()){
                  int newCount = magM.getOrDefault(c, 0)+1;
                  magM.put(c, newCount);
              }
              for (char c:ransomNote.toCharArray()){
                  int newCount = magM.getOrDefault(c,0)-1;
                  if (newCount<0)
                      return false;
                  magM.put(c, newCount);
              }
              return true;
          }
  
      }
  }
  
  ############
  
  class Solution {
      public boolean canConstruct(String ransomNote, String magazine) {
          int[] counter = new int[26];
          for (char c : magazine.toCharArray()) {
              ++counter[c - 'a'];
          }
          for (char c : ransomNote.toCharArray()) {
              if (counter[c - 'a'] <= 0) {
                  return false;
              }
              --counter[c - 'a'];
          }
          return true;
      }
  }
  

• // OJ: https://leetcode.com/problems/ransom-note/
  // Time: O(M + N)
  // Space: O(1)
  class Solution {
  public:
      bool canConstruct(string ransomNote, string magazine) {
          int cnt[26] = {0};
          for (char c : magazine) cnt[c - 'a']++;
          for (char c : ransomNote) {
              if (--cnt[c - 'a'] < 0) return false;
          }
          return true;
      }
  };
  

• class Solution:
      def canConstruct(self, ransomNote: str, magazine: str) -> bool:
          counter = Counter(magazine)
          for c in ransomNote:
              if counter[c] <= 0:
                  return False
              counter[c] -= 1
          return True
  
  ############
  
  class Solution(object):
    def canConstruct(self, ransomNote, magazine):
      """
      :type ransomNote: str
      :type magazine: str
      :rtype: bool
      """
      letters = [0] * 26
      for c in magazine:
        letters[ord(c) - ord('a')] += 1
  
      for c in ransomNote:
        if letters[ord(c) - ord('a')] == 0:
          return False
        else:
          letters[ord(c) - ord('a')] -= 1
      return True
  
  

• func canConstruct(ransomNote string, magazine string) bool {
  	rc := make([]int, 26)
  	for _, b := range ransomNote {
  		rc[b-'a']++
  	}
  
  	mc := make([]int, 26)
  	for _, b := range magazine {
  		mc[b-'a']++
  	}
  
  	for i := 0; i < 26; i++ {
  		if rc[i] > mc[i] {
  			return false
  		}
  	}
  	return true
  }
  
  

• function canConstruct(ransomNote: string, magazine: string): boolean {
      let counter = new Array(26).fill(0);
      let base = 'a'.charCodeAt(0);
      for (let s of magazine) {
          ++counter[s.charCodeAt(0) - base];
      }
      for (let s of ransomNote) {
          let idx = s.charCodeAt(0) - base;
          if (counter[idx] == 0) return false;
          --counter[idx];
      }
      return true;
  }
  
  

• class Solution {
      /**
       * @param String $ransomNote
       * @param String $magazine
       * @return Boolean
       */
      function canConstruct($ransomNote, $magazine) {
          $arrM = str_split($magazine);
          for ($i = 0; $i < strlen($magazine); $i++) {
              $hashtable[$arrM[$i]] += 1;
          }
          for ($j = 0; $j < strlen($ransomNote); $j++) {
              if (!isset($hashtable[$ransomNote[$j]]) || $hashtable[$ransomNote[$j]] == 0) return false;
              else $hashtable[$ransomNote[$j]] -= 1;
          }
          return true;
      }
  }
  

• public class Solution {
      public bool CanConstruct(string ransomNote, string magazine) {
          int[] cnt = new int[26];
          foreach (var c in magazine) {
              ++cnt[c - 'a'];
          }
          foreach (var c in ransomNote) {
              if (--cnt[c - 'a'] < 0) {
                  return false;
              }
          }
          return true;
      }
  }
  

All Problems

All Solutions