方法1:哈希表(效率较低)
时间复杂度:$O(m + n)$
空间复杂度:$O(Σ)$
解题思路
效率较低。官方题解只用一个大小为26的数组。
https://leetcode.cn/problems/ransom-note/solution/shu-jin-xin-by-leetcode-solution-ji8a/
Java 代码
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
if (ransomNote.length() > magazine.length()) {
return false;
}
Map<Character, Integer> map = new HashMap<>();
int len1 = ransomNote.length(), len2 = magazine.length();
for (int i = 0; i < len2; i ++) {
char m = magazine.charAt(i);
map.put(m, map.getOrDefault(m, 0) + 1);
}
for (int j = 0; j < len1; j ++) {
char r = ransomNote.charAt(j);
if (!map.containsKey(r) ||
map.get(r) == 0) {
return false;
} else {
map.put(r, map.getOrDefault(r, 0) - 1);
}
}
return true;
}
}