LeetCode 383.赎金信

前言

随着时间的推移，算法能力已经成为了衡量一个程序员好坏的标准，检查刷题已经可以称为是程序员的习惯，无论是为了找工作还是打比赛让我们一起刷题吧！
这篇文章是对于 Leetcode 383.赎金信 的题解。
下面是博主对于 Leetcode 383.赎金信 的一些看法与解决方式，附有代码和注释，请放心食用

一、题目描述与分析

题目描述：
前言有题目链接，可以直接去读原题。
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
目标就是判断 ransomNote 能不能由 magazine 里面的字符构成。

二、题解以及代码

博主对于题目的分析以及解决方法
1、哈希表
思路：使用哈希表来统计 magazine 中每个字符的出现次数，然后遍历 ransomNote 中的字符，对于每个字符，从哈希表中减去相应的次数，如果哈希表中字符的次数小于零或者字符不在哈希表中，则返回 false。如果遍历完 ransomNote 中的所有字符都没有问题，返回 true。
1）创建一个哈希表 charCount，用于统计 magazine 中每个字符的出现次数。
2）遍历 magazine 中的字符，将字符作为键，出现次数作为值，存储到 charCount 中。
3）遍历 ransomNote 中的字符，对于每个字符：

• 如果该字符在 charCount 中存在且次数大于零，将次数减一。
• 如果该字符不在 charCount 中或者次数已经为零，返回 false，因为无法构建 ransomNote。
• 如果遍历完 ransomNote 中的所有字符都没有问题，返回 true，表示可以构建 ransomNote。

复杂度分析：
1）时间复杂度：
遍历 magazine 中的字符需要 O(m) 的时间，其中 m 是 magazine 的长度。
遍历 ransomNote 中的字符需要 O(n) 的时间，其中 n 是 ransomNote 的长度。
统计字符出现次数和检查次数需要 O(1) 的时间（常数级别）。
因此，总时间复杂度是 O(m + n)。

2）空间复杂度：
哈希表 charCount 存储了 magazine 中字符的出现次数，最坏情况下会包含所有不同字符，因此空间复杂度是 O（c），其中 c 表示字符集中不同字符的数量。

public boolean canConstruct(String ransomNote, String magazine) {
    if (ransomNote == null || magazine == null) {
        return false;
    }

    Map<Character, Integer> charCount = new HashMap<>();
    
    // 统计 magazine 中每个字符的出现次数
    for (char c : magazine.toCharArray()) {
        charCount.put(c, charCount.getOrDefault(c, 0) + 1);
    }

    // 遍历 ransomNote 中的字符，减去对应次数
    for (char c : ransomNote.toCharArray()) {
        if (charCount.containsKey(c) && charCount.get(c) > 0) {
            charCount.put(c, charCount.get(c) - 1);
        } else {
            return false;
        }
    }

    return true;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

2、排序
思路：对 magazine 和 ransomNote 进行排序，然后使用双指针分别遍历这两个排序后的字符串。在遍历过程中，比较 magazine 中的字符和 ransomNote 中的字符是否匹配。如果能够匹配完整的 ransomNote，则返回 true；否则，返回 false。
1）将 ransomNote 和 magazine 分别转换成字符数组 ransomNoteChars 和 magazineChars。
2）对 ransomNoteChars 和 magazineChars 进行排序。
3）使用两个指针 i 和 j 分别初始化为 0，分别指向 ransomNoteChars 和 magazineChars。
4）在循环中，比较 ransomNoteChars[i] 和 magazineChars[j]，如果相等，增加 i 和 j，继续比较下一个字符，否则只增加 j，继续搜索匹配。
5）如果能够匹配完整的 ransomNoteChars，则返回 true，否则返回 false。

复杂度分析：
1）时间复杂度：
对 ransomNoteChars 和 magazineChars 进行排序需要 O(nlogn) 的时间，其中 n 是字符串的长度。
使用双指针遍历字符数组需要 O(n) 的时间。
因此，总时间复杂度是 O(nlogn)。

2）空间复杂度：
需要额外的空间存储字符数组 ransomNoteChars 和 magazineChars，空间复杂度是 O(n)。

public boolean canConstruct(String ransomNote, String magazine) {
    if (ransomNote == null || magazine == null) {
        return false;
    }

    char[] ransomNoteChars = ransomNote.toCharArray();
    char[] magazineChars = magazine.toCharArray();

    Arrays.sort(ransomNoteChars);
    Arrays.sort(magazineChars);

    int i = 0, j = 0;
    while (i < ransomNoteChars.length && j < magazineChars.length) {
        if (ransomNoteChars[i] == magazineChars[j]) {
            i++;
        }
        j++;
    }

    return i == ransomNoteChars.length;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3、数组计数
思路：对于英文字母的题目，可以使用一个长度为 26 的数组来记录字符的出现次数。首先，遍历 magazine，统计每个字符的出现次数，然后再遍历 ransomNote，对于每个字符，从数组中减去相应的次数，如果数组中字符的次数小于零或者字符不在数组中，则返回 false。如果遍历完 ransomNote 中的所有字符都没有问题，返回 true。

1）创建一个长度为 26 的整数数组 charCount，用于统计英文字母字符的出现次数。数组的下标表示字符，例如 charCount[0] 表示字符 ‘a’ 的出现次数。
2）遍历 magazine 中的字符，将每个字符映射到数组中的相应位置，即将字符 ‘a’ 映射到 charCount[0]、字符 ‘b’ 映射到 charCount[1]，依此类推。
3）遍历 ransomNote 中的字符，对于每个字符：

• 如果 charCount 中相应位置的计数大于零，表示该字符在 magazine 中存在，将该位置的计数减一。
• 如果 charCount 中相应位置的计数已经为零或者字符不在 magazine 中，返回 false。

4）如果遍历完 ransomNote 中的所有字符都没有问题，返回 true，表示可以构建 ransomNote。

复杂度分析：
1）时间复杂度：
遍历 magazine 中的字符需要 O(m) 的时间，其中 m 是 magazine 的长度。
遍历 ransomNote 中的字符需要 O(n) 的时间，其中 n 是 ransomNote 的长度。
统计字符出现次数和检查次数需要 O(1) 的时间（常数级别）。
因此，总时间复杂度是 O(m + n)。

2）空间复杂度：
数组 charCount 的长度为 26，空间复杂度是 O(26) = O(1)。

public boolean canConstruct(String ransomNote, String magazine) {
    if (ransomNote == null || magazine == null) {
        return false;
    }

    int[] charCount = new int[26]; // 用于统计字符出现次数的数组

    // 统计 magazine 中每个字符的出现次数
    for (char c : magazine.toCharArray()) {
        charCount[c - 'a']++;
    }

    // 遍历 ransomNote 中的字符，减去对应次数
    for (char c : ransomNote.toCharArray()) {
        if (charCount[c - 'a'] > 0) {
            charCount[c - 'a']--;
        } else {
            return false;
        }
    }

    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

总结

写题目时的一些想法以及收获
看见这个题目我第一个想到的就是使用哈希表，在写代码的过程中我遇见了许多问题，原因是对于哈希表的不熟悉，需要一边写一边查方法，不过到最后还是有惊无险的通过了，所以无论我们在刷题过程中遇见了什么困难我们也不要放弃，解决问题的过程本身也是加强我们自己的一种方式。
欢迎大家与博主交流题目，博主看见必回，大家可以在评论区或者直接私信来向博主提问题或者意见，以后博主还会持续更新刷题的内容，欢迎关注。