赎金信

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

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

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

示例 1：

1
2
输入：ransomNote = "a", magazine = "b"
输出：false

示例 2：

1
2
输入：ransomNote = "aa", magazine = "ab"
输出：false

示例 3：

1
2
输入：ransomNote = "aa", magazine = "aab"
输出：true

提示：

  • 1 <= ransomNote.length, magazine.length <= 105
  • ransomNote 和 magazine 由小写英文字母组成

这题很像上一道有效字母的异位词。

  • 使用哈希表记录ransomNote中每个字母出现的次数
  • 遍历magazine，如果发现该字母在ransomNote中出现过,将哈希表中对应次数减一，未完成的字母数减一
  • 如果字母全部处理完，返回true,否则返回false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int n = ransomNote.length();
        int[] table = new int[26];
        for(int i =0;i<n;i++){
            table[ransomNote.charAt(i)-'a']++;
        }
        for(int i=0;i<magazine.length();i++){
            if(table[magazine.charAt(i)-'a']>0){
                n--;
                table[magazine.charAt(i)-'a']--;
            }
        }
        return n==0?true:false;
    }
}