力扣383.赎金信(java语言散列表法)

赎金信(java语言散列表法)"/>

力扣383.赎金信(java语言散列表法)

题目描述：

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

解题思路：

此题我们抽象出来的问题就是在ransomNote中的字符个数是否大于等于magazine 中对应字符的个数，此时我们就又可以发现再这个抽象出来待解决的问题中存在着一个映射关系，所以我们可以想到用散列表这个数据结构来解决此题,具体操作如下（该操作涉及到本类型题目操作的一个解题技巧，该技巧可参考本人另一篇文章力扣242.有效的字母异位词(Java语言，排序法、散列表法)）：

手动创建一个26int类型长度的数组
先将ransomNote中每个字符依次减去’a’作为索引，再将该索引处的值加1
再将magazine中每个字符依次减去‘a’作为索引，将该索引处的值减一并且判断，若此时该索引处值小于0则说明ransomNote中对应字符的个数小于等于magazine中对应得字符，或者ransomNote中不存在magazine中字符，反知易得。

代码：

class Solution {//HashTable//Time Complexity: O(N)//Space Complexity: O(M)	此处M为26public boolean canConstruct(String ransomNote, String magazine) {//如果rangsomNote得长度大于magazine得长度//则直接不符合if (rangsomNotee.length() > magazine.length()) {return false;}//创建哈希表int[] table = new int[26];//先存入magazinefor (int i = 0; i < magazine.length(); i++) {table[magazine.charAt(i) - 'a']++;}//再存入magazine，并判断for (int j = 0; j < ransomNote.length(); j++) {table[ransomNote.charAt(j) - 'a']--;if (table[ransomNote.charAt(j) - 'a'] < 0) {return false;}}return true;}
}