383. 赎金信

给你两个字符串：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 由小写英文字母组成

题解

哈希表法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public static boolean canConstruct(String ransomNote, String magazine) {
    //如果ransomNote的长度大于magazine则肯定没法构成，直接返回false
    if (ransomNote.length() > magazine.length()) {
        return false;
    }

    //将magazine中的字符作为键，出现次数作为值，存入哈希表
    HashMap<Character, Integer> map = new HashMap<>();

    for (int i = 0; i < magazine.length(); i++) {
        char c = magazine.charAt(i);
        map.put(c, map.getOrDefault(c, 0) + 1);
    }


    //将map中存储的字符进行取出，用来构建ransomNote看是否能成功
    for (int i = 0; i < ransomNote.length(); i++) {
        char c = ransomNote.charAt(i);
        //若ransomNote中存在magazine没有的字符，直接返回false
        if (map.keySet().contains(c)) {
            int count = map.get(c);
            //若存在，更新字符个数
            if (count > 0) {
                map.put(c, --count);
                //字符个数不够，返回false
            } else {
                return false;
            }
        } else {
            return false;
        }

    }
    return true;

}
  • 时间复杂度:O(m + n)，m和n分别为两个字符串的长度
  • 空间复杂度:O(∣S∣)，S 是字符集，这道题中 S 为全部小写英语字母，因此 |S| = 26。