Question
Formatted question description: https://leetcode.ca/all/383.html
383 Ransom Note
Given an arbitrary ransom note string and another string containing letters from all the magazines,
write a function that will return true if the ransom note can be constructed from the magazines ;
otherwise, it will return false.
Each letter in the magazine string can only be used once in your ransom note.
Note:
You may assume that both strings contain only lowercase letters.
canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true
Algorithm
Hash Map counts the number of characters.
Code
Java
-
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; } } }
-
// 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(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