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
andmagazine
consist of lowercase English letters.
Algorithm
Hash Map counts the number of characters.
Code
-
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; } }