题目
题目来源leetcode
leetcode地址：383. 赎金信，难度：简单。
题目描述(摘自leetcode)：
给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。 (题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。) 示例 1： 输入：ransomNote = "a", magazine = "b" 输出：false 示例 2： 输入：ransomNote = "aa", magazine = "ab" 输出：false 示例 3： 输入：ransomNote = "aa", magazine = "aab" 输出：true 提示： 你可以假设两个字符串均只含有小写字母。
本地调试代码：
class Solution { public boolean canConstruct(String ransomNote, String magazine) { ... } public static void main(String[] args) { System.out.println(new Solution().canConstruct("a", "ab")); } }
题解
NO1：哈希解法
思路： 这里题目提示说只有小写字母，可以直接通过数组来进行解决。数组对应的索引表示指定的字符，索引位置的值表示出现的次数(第一次遍历杂志字符串)，之后遍历赎金信字符串遍历的每个字符来进行抵消之前的数量。
代码：
public boolean canConstruct(String ransomNote, String magazine) { //若是赎金信字符串的长度大于杂志字符串，直接返回 if(ransomNote.length() > magazine.length()){ return false; } int[] chArray = new int[26]; //遍历杂志字符串，对应的索引值表示该字符出现的次数 for (char ch : magazine.toCharArray()) { chArray[ch-'a']++; } //遍历赎金信字符串，每个字符先判断是否存在，若是不存在直接返回，这里是否存在使用0来表示 for (char ch : ransomNote.toCharArray()) { if(chArray[ch-'a'] == 0){ return false; } chArray[ch-'a']--; } return true; }
