赎金信-力扣383
目录
赎金信 力扣383
一、题目
二、思路
题目要求判断一个赎金信字符串 ransomNote 是否可以由杂志字符串 magazine 中的字符构成。每个字符只能使用一次，且假设两个字符串均只含有小写字母。
该问题可以通过统计字符频率来解决。具体步骤如下：
1.创建一个长度为26的整型数组 arr，用于记录每个字母在 ransomNote 中出现的次数。数组索引0对应字母’a’，索引1对应’b’，以此类推。
2.遍历 ransomNote 字符串，对于每个字符，计算其在数组中的索引（即 char - ‘a’），并将对应位置的值加1。
3.遍历 magazine 字符串，对于每个字符，检查其在数组中的索引位置是否大于0（即该字符在 ransomNote 中出现过）。如果是，则将对应位置的值减1。
4.最后遍历字符频率数组 arr，如果所有位置的值都为0，说明 magazine 中的字符足够构成 ransomNote，返回 true；否则返回 false。
三、代码
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
//空间换时间
int[] arr = new int[26];
for (int i = 0; i < ransomNote.length(); i++) {
arr[ransomNote.charAt(i) - 'a']++;
}
for (int i = 0; i < magazine.length(); i++) {
//加这个判断条件是为了防止-1的出现
//只减去ransomNote中出现的字符
//不加这个if判断就会出现负数，导致结果不正确 比如‘aa’ 和‘aab’
if(arr[magazine.charAt(i) - 'a'] > 0){
arr[magazine.charAt(i) - 'a']--;
}
}
for (int i = 0; i < arr.length; i++) {
if (arr[i] != 0) {
return false;
}
}
return true;
}
}