383. 赎金信

1. 题目

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

2. 思路

  • 由于题目中的ransomNote 和 magazine 由小写英文字母组成，因此初始化map数组大小为26，对应26个小写英文字母
  • 并逐一将magazine变量中的字符逐一置入对应的下标中
  • 遍历ransomNote字符数组，如果出现ransomNote中的字符在map中的计数为0，则说明magazine字符串中的字符无法拼凑出ransomNote，此时可以直接返回结果false

3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        var map = new int[26];

        for (var i = 0; i < magazine.length(); ++i) {
            map[getIndex(magazine.charAt(i))]++;
        }
        
        for (var i = 0; i < ransomNote.length(); ++i) {
            var mapIndex = getIndex(ransomNote.charAt(i));
            if (map[mapIndex] <= 0) {
                return false;
            }
            map[mapIndex]--;
        }

        return true;
    }

    private int getIndex(char ch) {
        return ch - 'a';
    }
}

4. 复杂度

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

image-20230825214030456