江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode 第383题：赎金信

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。

📖 文章摘要

本文详细解析LeetCode第383题“赎金信”，这是一道字符串处理题。文章提供了基于哈希表的解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要提升字符串处理能力的读者。

核心知识点： 字符串、哈希表、计数 难度等级： 简单 推荐人群： 具有基础算法知识，想要提升字符串处理能力的程序员

题目描述

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。

示例

示例 1：

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

示例 2：

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

示例 3：

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

提示

  • 你可以假设两个字符串均只含有小写字母。

解题思路

本题可以使用哈希表解决：

  1. 统计magazine中每个字符的出现次数
  2. 遍历ransomNote，检查每个字符是否可用
  3. 如果字符不可用，返回false
  4. 如果所有字符都可用，返回true

时间复杂度： O(m + n) 空间复杂度： O(1)

图解思路

字符统计

字符 magazine ransomNote 结果
a 2 2 可用
b 1 0 可用
c 0 0 可用

处理流程

步骤 操作 说明
1 统计magazine 记录每个字符出现次数
2 遍历ransomNote 检查字符是否可用
3 返回结果 根据检查结果返回

代码实现

C# 实现

public class Solution {
    public bool CanConstruct(string ransomNote, string magazine) {
        int[] count = new int[26];
        
        foreach (char c in magazine) {
            count[c - 'a']++;
        }
        
        foreach (char c in ransomNote) {
            if (--count[c - 'a'] < 0) {
                return false;
            }
        }
        
        return true;
    }
}

Python 实现

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        count = [0] * 26
        
        for c in magazine:
            count[ord(c) - ord('a')] += 1
            
        for c in ransomNote:
            count[ord(c) - ord('a')] -= 1
            if count[ord(c) - ord('a')] < 0:
                return False
                
        return True

C++ 实现

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        vector<int> count(26, 0);
        
        for (char c : magazine) {
            count[c - 'a']++;
        }
        
        for (char c : ransomNote) {
            if (--count[c - 'a'] < 0) {
                return false;
            }
        }
        
        return true;
    }
};

执行结果

C# 实现

  • 执行用时：92 ms
  • 内存消耗：24.8 MB

Python 实现

  • 执行用时：28 ms
  • 内存消耗：13.2 MB

C++ 实现

  • 执行用时：4 ms
  • 内存消耗：8.4 MB

性能对比

语言 执行用时 内存消耗 特点
C++ 4 ms 8.4 MB 执行效率最高，内存占用最小
Python 28 ms 13.2 MB 代码简洁，内存占用适中
C# 92 ms 24.8 MB 类型安全，内存占用较大

代码亮点

  1. 🎯 使用数组代替哈希表优化性能
  2. 💡 空间复杂度优化
  3. 🔍 处理边界情况
  4. 🎨 代码结构清晰，易于维护

常见错误分析

  1. 🚫 未考虑字符顺序
  2. 🚫 统计错误
  3. 🚫 边界条件处理错误
  4. 🚫 空间复杂度优化不足

解法对比

解法 时间复杂度 空间复杂度 优点 缺点
数组计数 O(m + n) O(1) 高效，空间优 仅适用于小写字母
哈希表 O(m + n) O(k) 通用 空间占用较大

相关题目

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第383题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

  • 👍 点个赞，让更多人看到这篇文章
  • 📁 收藏文章，方便后续查阅复习
  • 🔔 关注作者，获取更多高质量算法题解
  • 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！